var distances = [
       0,     404,    2126,    4193,    3219,    3886,    3951,    4363,    4613,    5360,
    4930,    5640,    5481,    5447,    3649,    6720,    5629,    5787,    6316,    7844,
    5888,    6407,    8004,    6230,    8423,    7710,    4977,    6790,    6379,    7685,
    7029,    5671,    6309,    6413,    6147,    6132,    7050,    6251,    6382,    6433,
    6821,    7016,    6644,    6760,    6977,    7366,    6917,    6729,    7309,    7550,
    7125,    7486,    7628,    7849,    7957,    7852,    7969,    6614,    7578,    7858,
    8163,    8621,    8073,    8413,    8243,    7896,    7438,    8662,    9148,    8391,
    8621,    8539,    9016,    8796,    8962,    9383,    9438,    9393,    9536,    9345,
   10494,    9637,    9783,   10019,    9687,   10157,   10077,   10158,   10000,   10457,
   10167,   10622,   10618,   10617,   10737,   10701,   11434,   10950,   11294,   12038,
   12157,   11890,   12375,   11640,   13056,   14027,   13021,   11488,   12364,   11813,
   13224,   12717,   14697,   14259,    9752,   10790,   10115,   11245,   11851,   11583,
   10840,   11360,   11933,   12084,   12359,   12297,    9120,   12864,   11902,     404,
       0,    1716,    3789,    2810,    3482,    3541,    3953,    4203,    4950,    4520,
    5236,    5071,    5037,    3239,    6310,    5219,    5377,    5906,    7440,    5478,
    5997,    7594,    5820,    8019,    7306,    4567,    6386,    5969,    7281,    6619,
    5262,    5900,    6004,    5743,    5722,    6646,    5841,    5972,    6023,    6411,
    6607,    6235,    6351,    6573,    6962,    6507,    6325,    6900,    7141,    6716,
    7076,    7218,    7445,    7548,    7442,    7559,    6204,    7169,    7449,    7759,
    8217,    7663,    8004,    7834,    7487,    7029,    8253,    8740,    7982,    8212,
    8129,    8612,    8387,    8553,    8974,    9029,    8984,    9127,    8941,   10085,
    9228,    9374,    9615,    9278,    9753,    9668,    9749,    9591,   10048,    9758,
   10213,   10214,   10208,   10328,   10292,   11030,   10541,   10885,   11629,   11753,
   11481,   11966,   11231,   12647,   13623,   12612,   11084,   11955,   11404,   12815,
   12308,   14288,   13855,    9348,   10386,    9711,   10841,   11447,   11179,   10436,
   10956,   11529,   11680,   11955,   11893,    8716,   12460,   11498,    2126,    1716,
       0,    2299,    1936,    2006,    2289,    2506,    2742,    3489,    3073,    3746,
    3624,    3576,    1887,    4846,    3967,    3937,    4524,    5950,    4042,    4615,
    6234,    4383,    6529,    5816,    3131,    4896,    4717,    5791,    5183,    4412,
    5003,    5068,    4267,    4261,    5170,    4380,    4511,    4562,    4950,    4886,
    5385,    5252,    5097,    5337,    5046,    4849,    5662,    5808,    5632,    5615,
    5757,    5969,    6102,    5981,    6098,    4743,    6170,    6398,    6283,    6664,
    6202,    6566,    6517,    6258,    6104,    7162,    6948,    6958,    6858,    6668,
    7136,    7288,    7282,    7624,    7903,    7539,    7708,    7465,    7901,    7957,
    8000,    8139,    8007,    8277,    8600,    8651,    8303,    8777,    8313,    8755,
    8738,    8860,    9478,    9217,    9554,    9270,    9870,   10458,   10277,   10553,
   10816,   10130,   11202,   12147,   11341,    9608,   10510,   10453,   11829,   11322,
   12866,   12379,    7872,    8910,    8235,    9365,    9971,    9703,    8960,    9480,
   10053,   10204,   10479,   10417,    7240,   10984,   10022,    4101,    3697,    2200,
       0,    2347,    2405,    1567,    4147,    2143,    3767,    3870,    2526,    4591,
    3411,     476,    3627,    2917,    2718,    3305,    4731,    2823,    3396,    5015,
    3164,    5310,    4597,    1912,    3677,    4172,    4572,    3964,    5973,    5402,
    5467,    4666,    4118,    4981,    4319,    4569,    4467,    4884,    5747,    5907,
    5651,    5496,    5297,    5071,    4660,    6061,    6475,    6031,    5446,    5653,
    5780,    6501,    5877,    5500,    4566,    6569,    6797,    6682,    6589,    6147,
    6965,    6916,    6657,    6503,    7561,    6888,    7357,    7257,    6608,    7535,
    7687,    8048,    8023,    8302,    7938,    8107,    7382,    7758,    8386,    8399,
    8538,    8436,    8676,    8999,    9050,    8702,    9373,    8712,    9154,    9137,
    9259,   10020,    9616,    9953,    9894,   10269,   10857,   10676,   10952,   11215,
   10529,   11601,   12546,   12181,   10007,   10909,   10852,   12228,   11721,   13265,
   12778,    7683,    8721,    8046,    9176,    9782,    9514,    8771,    9291,    9864,
   10015,   10290,   10228,    7051,   10795,    9833,    3219,    2810,    1960,    2412,
       0,    2068,    2295,    2540,    2803,    3550,    3107,    3835,    2885,    3637,
    1993,    4959,    3973,    4050,    4637,    6063,    4155,    4728,    6347,    4496,
    6642,    5929,    3244,    5009,    4723,    5904,    5296,    2466,    3104,    3208,
    2960,    3584,    5356,    4145,    4820,    4559,    4230,    3811,    3439,    3555,
    3790,    4240,    4738,    4911,    4104,    4345,    3920,    4809,    5204,    5041,
    4752,    5401,    5844,    4817,    4373,    4653,    4976,    5434,    5510,    5208,
    5038,    4691,    4233,    5457,    5944,    5186,    5416,    5971,    5829,    5591,
    5757,    6178,    6233,    6188,    6331,    6158,    7289,    6432,    6578,    6832,
    6482,    6970,    6872,    6953,    6795,    7252,    6962,    7417,    7431,    7412,
    7532,    7496,    8247,    7745,    8089,    8833,    8970,    8685,    9170,    8435,
    9851,   10840,    9816,    8301,    9159,    8608,   10019,    9512,   11492,   11072,
    7437,    8884,    8209,    9047,    9693,    8792,    8392,    9454,   10027,    9385,
   10453,   10336,    7133,   10958,    9454,    3882,    3478,    2048,    2466,    2064,
       0,    1258,     635,     694,    1441,    1252,    1878,    1803,    1528,    1778,
    4849,    3758,    3916,    4445,    6117,    4017,    4536,    6133,    4359,    6696,
    5983,    3106,    3286,    2824,    5958,    5158,    3130,    2956,    3247,    2475,
    2213,    3382,    2332,    2463,    2514,    2902,    3195,    3446,    3550,    3395,
    3289,    2998,    3063,    3960,    3877,    3760,    3567,    3709,    4028,    4394,
    3933,    4050,    2695,    4468,    4547,    4581,    4616,    4154,    4864,    4815,
    4556,    4272,    5460,    4900,    5168,    5120,    4620,    5434,    5573,    5461,
    5922,    6201,    5837,    5783,    5459,    5853,    6136,    6282,    6362,    6186,
    6500,    6643,    6949,    6499,    6956,    6611,    7053,    7025,    7116,    7590,
    7270,    7852,    7449,    8168,    8692,    8575,    8782,    9114,    8428,    9500,
   10445,    9520,    7810,    8808,    8705,   10116,    9609,   11164,   10677,    5967,
    7177,    6502,    7632,    8238,    7970,    7227,    7747,    8320,    8471,    8746,
    8684,    5470,    9251,    8289,    3951,    3541,    2289,    1895,    2295,    1258,
       0,    1425,     769,    1367,    2162,    2051,    2730,    2210,    1132,    3523,
    2432,    2590,    3119,    5464,    2691,    3210,    4807,    3033,    6043,    5330,
    1780,    3223,    2761,    4610,    3832,    4060,    3886,    4197,    3405,    2895,
    4006,    3014,    3145,    3196,    3584,    3877,    4376,    4644,    4174,    3971,
    3680,    3685,    5054,    4559,    4657,    4249,    4391,    4710,    4978,    4615,
    4732,    3377,    5562,    5444,    5419,    5298,    4836,    5958,    5909,    5570,
    5183,    6554,    5582,    6065,    6017,    5302,    6209,    6470,    6358,    6987,
    7295,    6789,    6465,    6141,    6535,    7033,    7179,    7044,    7083,    7182,
    7540,    8043,    7396,    7853,    7563,    8018,    7707,    8013,    8487,    8167,
    8907,    8346,    9262,    9589,    9569,    9945,   10208,    9522,   10452,   11539,
   10417,    8707,    9760,    9649,   11221,   10714,   12258,   11771,    6649,    7746,
    7071,    8201,    8807,    8539,    7796,    8316,    8889,    9040,    9315,    9253,
    6076,    9820,    8858,    4357,    3953,    2506,    2751,    2539,     635,    1425,
       0,     826,    1573,     828,    2010,    1415,    1072,    2413,    4948,    3857,
    4015,    4544,    6320,    4116,    4985,    6232,    4491,    6782,    6186,    3205,
    3471,    2916,    5798,    5257,    2772,    2598,    3059,    2117,    1757,    2926,
    1876,    2007,    2058,    2446,    2739,    3088,    3483,    3036,    2833,    2542,
    2607,    3893,    3421,    3519,    3111,    3253,    3572,    3840,    3477,    3594,
    2239,    4112,    4306,    4281,    4160,    3698,    4797,    4748,    4432,    4045,
    5196,    4444,    4927,    4879,    4164,    5071,    5332,    5220,    5849,    5972,
    5651,    5327,    5003,    5397,    5895,    6041,    5906,    5945,    6044,    6402,
    6692,    6258,    6715,    6425,    6880,    6569,    6875,    7349,    7029,    7769,
    7208,    7828,    8451,    8431,    8424,    8909,    8174,    9314,   10378,    9279,
    7569,    8622,    8511,    9758,    9251,   11097,   10610,    5511,    6921,    6166,
    7253,    8101,    7833,    6928,    7491,    8183,    8334,    8609,    8267,    5014,
    9024,    8108,    4613,    4203,    2742,    1807,    2803,     694,     769,     826,
       0,     747,    1563,    1404,    2131,    1611,    1844,    4076,    2985,    3143,
    3672,    5376,    3244,    3763,    5360,    3586,    5955,    5242,    2333,    2780,
    2318,    5217,    4385,    3507,    3333,    3598,    2852,    2296,    3443,    2415,
    2546,    2597,    2985,    3278,    4294,    4058,    3575,    3372,    3081,    3122,
    4491,    3960,    4058,    3650,    3792,    4111,    4379,    4016,    4133,    2778,
    4999,    4845,    4820,    4699,    4237,    5395,    5318,    4971,    4584,    5991,
    4983,    5466,    5418,    4703,    5610,    5871,    5759,    6388,    6732,    6190,
    5866,    5542,    5936,    6434,    6580,    6445,    6484,    6583,    6941,    7480,
    6797,    7254,    6964,    7419,    7108,    7414,    7888,    7568,    8308,    7747,
    8699,    8990,    8970,    9382,    9645,    8959,    9853,   10976,    9818,    8108,
    9161,    9050,   10658,   10151,   11695,   11208,    6050,    7183,    6508,    7638,
    8244,    7976,    7233,    7753,    8326,    8477,    8752,    8690,    5513,    9257,
    8295,    5360,    4950,    3489,    2275,    3550,    1441,    1367,    1573,     747,
       0,    1401,     867,    1580,    1000,    2442,    4511,    3420,    3578,    4107,
    5844,    3679,    4419,    5795,    3446,    6052,    5643,    2768,    2281,    1819,
    4753,    4820,    3150,    2892,    2987,    2305,    1685,    2570,    1804,    1935,
    1986,    2374,    2667,    3546,    3290,    2964,    2761,    2470,    2249,    3700,
    3349,    3447,    3035,    3181,    3369,    3768,    3405,    3522,    2155,    4208,
    4234,    4152,    4088,    3626,    4604,    4555,    4296,    3973,    5200,    4372,
    4855,    4727,    4092,    4999,    5260,    5148,    5662,    5941,    5408,    5255,
    4931,    5325,    5823,    5869,    5834,    5873,    5972,    6330,    6689,    6172,
    6643,    6182,    6624,    6497,    6729,    7277,    6957,    7423,    7136,    7908,
    8379,    8146,    8591,    8854,    8168,    9071,   10185,    9207,    7477,    8379,
    8439,    9867,    9360,   10904,   10417,    5272,    6310,    5635,    6765,    7371,
    7103,    6360,    6880,    7453,    7604,    7879,    7817,    4640,    8384,    7422,
    4924,    4520,    3073,    3508,    3106,    1252,    2073,     742,    1495,    1466,
       0,    1555,     586,     704,    3030,    5794,    4594,    4885,    5472,    6691,
    4232,    5020,    6176,    3851,    5756,    5347,    3942,    3113,    2558,    5018,
    5547,    1982,    1808,    2099,    1327,    1399,    2274,    1518,    1649,    1700,
    2088,    1726,    2298,    2312,    2157,    2151,    2184,    1953,    2722,    2530,
    2453,    2739,    2895,    3073,    3087,    3119,    3236,    1859,    3230,    3240,
    3343,    3801,    3340,    3626,    3577,    3318,    3124,    4222,    4086,    3861,
    3813,    3806,    4196,    4266,    4154,    4684,    4963,    4585,    4724,    4525,
    5039,    4829,    4975,    5199,    4879,    5337,    5336,    5711,    5192,    5649,
    5359,    5814,    5798,    5809,    6283,    5963,    6614,    6142,    6930,    7385,
    7337,    7613,    7876,    7190,    8248,    9207,    8213,    6503,    7556,    7513,
    8889,    8382,    9926,    9439,    4976,    6014,    5339,    6469,    7075,    6807,
    6064,    6584,    7157,    7752,    7583,    7521,    4344,    8088,    7126,    5623,
    5219,    3740,    2195,    3817,    1878,    1920,    2010,    1527,     867,    1507,
       0,    1669,    1089,    2633,    4350,    3259,    3417,    3946,    5832,    3091,
    3612,    4981,    2639,    4897,    4488,    2607,    1474,    1012,    3946,    4374,
    3239,    2981,    3076,    2411,    1774,    2676,    1893,    1707,    2075,    2463,
    2756,    3652,    3396,    3053,    2850,    2559,    2355,    3806,    3438,    3536,
    3128,    3270,    3475,    3857,    3494,    3587,    2123,    4314,    4323,    4258,
    4177,    3715,    4710,    4661,    4402,    4062,    5306,    4461,    4944,    4833,
    4181,    5088,    5349,    5237,    5768,    6047,    5514,    5344,    5020,    5414,
    5912,    5975,    5923,    5962,    6061,    6419,    6795,    6275,    6732,    6288,
    6730,    6586,    6835,    7366,    7046,    7529,    7225,    8014,    8468,    8252,
    8697,    8960,    8274,    9177,   10291,    9296,    7583,    8485,    8528,    9973,
    9466,   11010,   10523,    5378,    6416,    5741,    6871,    7477,    7209,    6466,
    6986,    7559,    7710,    7985,    7923,    4746,    8490,    7528,    5481,    5071,
    3624,    4095,    2889,    1803,    2730,    1329,    2131,    1580,     586,    1669,
       0,     789,    3581,    5879,    5169,    4970,    5557,    6776,    4317,    5105,
    6261,    3936,    5841,    5432,    4211,    3242,    2650,    5103,    5632,    1393,
    1215,    1407,     734,    1153,    2359,    1632,    1778,    1829,    1534,    1140,
    1705,    1867,    1599,    1565,    2190,    2038,    2416,    1944,    1867,    2215,
    2592,    2459,    2501,    2816,    3169,    1944,    2729,    2654,    2830,    3017,
    2883,    3319,    3127,    2780,    2393,    3813,    3693,    3275,    3227,    3349,
    3766,    3680,    3568,    4197,    4589,    3999,    4138,    4023,    4582,    4243,
    4389,    4717,    4293,    4855,    4750,    5309,    4606,    5063,    4773,    5228,
    5782,    5223,    5697,    5377,    6117,    5556,    6445,    6799,    6779,    7041,
    7526,    6791,    7662,    9319,    7627,    5917,    6970,    6859,    8375,    7868,
    9848,    9602,    4847,    6099,    5424,    6554,    7160,    6603,    6149,    6669,
    7242,    7268,    7668,    7606,    4429,    8173,    7211,    5447,    5037,    3576,
    3388,    3637,    1528,    2158,    1072,    1580,    1000,     633,    1089,     824,
       0,    3091,    5089,    4379,    4180,    4767,    5986,    3527,    4315,    5471,
    3146,    5051,    4642,    3631,    2417,    1860,    4313,    4842,    2149,    1891,
    2005,    1349,     703,    1569,     822,     953,    1004,    1392,    1685,    2640,
    2384,    1965,    1779,    1488,    1248,    2794,    2367,    2465,    2034,    2199,
    2368,    2786,    2423,    2540,    1154,    3302,    3252,    3151,    3106,    2644,
    3698,    3649,    3378,    2972,    4294,    3390,    3873,    3726,    3110,    4004,
    4278,    4166,    4756,    5035,    4407,    4273,    3949,    4343,    4841,    4868,
    4852,    4891,    4990,    5348,    5783,    5171,    5661,    5181,    5623,    5515,
    5728,    6295,    5975,    6422,    6154,    7002,    7383,    7145,    7685,    7948,
    7262,    8070,    9279,    8225,    6476,    7378,    7457,    8961,    8454,    9998,
    9511,    4271,    5309,    4634,    5764,    6370,    6102,    5359,    5879,    6452,
    6603,    6878,    6816,    3639,    7383,    6421,    3649,    3239,    1852,     609,
    1993,    1778,    1132,    2413,    1844,    2442,    3030,    2632,    3581,    3093,
       0,    3743,    2633,    2788,    3317,    4847,    2939,    3501,    5005,    3280,
    5426,    4713,    2028,    3793,    3473,    4688,    4080,    4445,    5054,    5119,
    4253,    3778,    4947,    3897,    4028,    4079,    4467,    4760,    5418,    5303,
    5057,    4854,    4563,    4628,    5713,    5442,    5540,    5132,    5274,    5593,
    5861,    5498,    5615,    4260,    6221,    6449,    6302,    6181,    5719,    6617,
    6568,    6309,    6155,    7213,    6465,    6948,    6900,    6185,    7092,    7339,
    7241,    7675,    7954,    7590,    7348,    7024,    7418,    7916,    8051,    7927,
    7966,    8065,    8651,    8702,    8279,    8736,    8364,    8806,    8590,    8896,
    9511,    9268,    9605,    9229,    9921,   10509,   10328,   10604,   10867,   10181,
   11253,   12198,   11300,    9590,   10561,   10504,   11880,   11373,   12917,   12430,
    7532,    8942,    8187,    9274,   10022,    9754,    8949,    9512,   10104,   10255,
   10530,   10288,    7035,   11035,   10073,    6697,    6293,    4814,    3213,    4891,
    4849,    3523,    4948,    4076,    4511,    5930,    4350,    6308,    5483,    3651,
       0,    1251,    1068,     603,    2434,    1829,    1667,    2239,    2368,    3577,
    2924,    1965,    3163,    3821,    2855,    2077,    7464,    7096,    6792,    6637,
    5678,    5800,    5599,    4900,    5781,    6169,    6462,    7488,    7252,    6759,
    6556,    6265,    5840,    7801,    7144,    7252,    6834,    6459,    7295,    7563,
    6888,    6514,    5316,    8411,    8039,    8004,    7883,    7421,    8704,    8512,
    8165,    7778,    9495,    8001,    8660,    8612,    7721,    8563,    9065,    8953,
    9582,   10271,    9030,    8819,    8495,    8339,    9628,    9420,    9147,    9678,
    9495,   10135,   10706,    9991,   10448,    9804,    9763,    9885,   10608,   11082,
   10762,   10667,   10456,   12127,   12184,   12164,   12723,   13208,   12473,   12132,
   15001,   12485,   11302,   11440,   12244,   14057,   13550,   15530,   15390,    8054,
    9284,    8529,    9616,   10345,   10210,    9471,    9854,    9777,   10428,   10203,
   10610,    7593,   11226,   10651,    5629,    5219,    3967,    2533,    3973,    3758,
    2432,    3857,    2985,    3420,    4594,    3259,    5588,    4763,    2633,    1328,
       0,     408,     924,    2629,    1115,    1441,    2633,    1681,    3513,    2800,
     917,    2476,    3101,    2758,    2067,    6744,    6376,    6072,    5917,    4958,
    5080,    4879,    4180,    5061,    5449,    5742,    6768,    6532,    6039,    5836,
    5545,    5120,    7081,    6424,    6532,    6114,    5739,    6575,    6843,    6168,
    5794,    4596,    7691,    7319,    7284,    7163,    6701,    7984,    7792,    7445,
    7058,    8775,    7281,    7940,    7892,    7001,    7843,    8345,    8233,    8862,
    9551,    8310,    8099,    7775,    7619,    8908,    8700,    8678,    8958,    8816,
    9415,    9986,    9271,    9728,    9084,    9160,    9395,    9888,   10362,   10042,
   10049,    9736,   11407,   11464,   11444,   12003,   12488,   11753,   11697,   14281,
   11765,   10582,   11005,   11524,   13337,   12830,   14810,   14703,    7334,    8564,
    7809,    8896,    9625,    9490,    8751,    9134,    9057,    9708,    9483,    9890,
    6873,   10506,    9931,    5787,    5377,    3976,    2375,    4053,    3916,    2590,
    4015,    3143,    3578,    5092,    3417,    5375,    4550,    2788,    1068,     408,
       0,     664,    2424,     739,    1034,    2226,    1468,    3149,    2436,    1032,
    2277,    2888,    2351,    1660,    6531,    6163,    5859,    5704,    4745,    4867,
    4666,    3967,    4848,    5236,    5529,    6555,    6319,    5826,    5623,    5332,
    4907,    6868,    6211,    6319,    5901,    5526,    6362,    6630,    5955,    5581,
    4383,    7478,    7106,    7071,    6950,    6488,    7771,    7579,    7232,    6845,
    8562,    7068,    7727,    7679,    6788,    7630,    8132,    8020,    8649,    9338,
    8097,    7886,    7562,    7406,    8695,    8487,    8465,    8745,    8603,    9202,
    9773,    9058,    9515,    8871,    8947,    9182,    9675,   10149,    9829,    9836,
    9523,   11194,   11251,   11231,   11790,   12275,   11540,   11484,   14068,   11552,
   10369,   10792,   11311,   13124,   12617,   14597,   14506,    7121,    8351,    7596,
    8683,    9412,    9277,    8538,    8921,    8844,    9495,    9270,    9677,    6660,
   10293,    9718,    6316,    5906,    4652,    3051,    4660,    4445,    3119,    4544,
    3672,    4107,    5768,    3946,    5904,    5079,    3317,     603,     924,     664,
       0,    1843,    1426,    1081,    2000,    1997,    2986,    2333,    1561,    2806,
    3417,    2278,    1504,    7060,    6692,    6388,    6233,    5274,    5396,    5195,
    4496,    5377,    5765,    6058,    7084,    6848,    6355,    6152,    5861,    5436,
    7397,    6740,    6848,    6430,    6055,    6891,    7159,    6484,    6110,    4912,
    8007,    7635,    7600,    7479,    7017,    8300,    8108,    7761,    7374,    9091,
    7577,    8256,    8208,    7297,    8159,    8661,    8549,    9178,    9867,    8626,
    8387,    7887,    7935,    9224,    9016,    8561,    9274,    8909,    9731,   10302,
    9587,    9918,    9257,    9177,    9299,    9859,   10678,   10358,   10081,    9917,
   11584,   11514,   11276,   12256,   12519,   11833,   11546,   13792,   12081,   10607,
   10854,   11840,   13532,   13025,   14511,   14000,    7650,    8880,    8125,    9212,
    9941,    9806,    9067,    9450,    9304,   10024,    9730,   10206,    7189,   10754,
   10148,    7933,    7529,    6050,    4449,    6127,    6185,    4921,    7662,    5497,
    7121,    7793,    5880,    8607,    7392,    4887,    2464,    2729,    2508,    1836,
       0,    2632,    2117,     547,    3033,    1406,    1581,    3356,    4062,    8117,
    2224,    1240,   10352,    9781,    9846,    9030,    7522,    6724,    7767,    8017,
    7915,    8332,    9242,    9844,    9381,    8991,    8745,    8519,    6764,    9877,
    9911,    9485,    8894,    7130,    9228,    9937,    7467,    7000,    8014,   10467,
   10251,    9988,    8204,    7917,   10781,   10646,   10387,    9957,   11459,    8014,
    9288,    8918,    7734,    8633,    9525,    9327,   10152,   12200,    9125,    8824,
    8324,    8934,    9809,    9586,    8998,    9859,    9346,   10776,   12948,   10125,
   10355,    9694,    9614,    9736,   10296,   12146,   10997,   10518,   10354,   12021,
   11951,   11713,   12693,   12956,   12270,   11983,   14229,   12810,   11044,   11291,
   12511,   13969,   13462,   14948,   14437,    8435,    9704,    9029,   10159,   10765,
   10266,    9523,   10274,    9741,   10767,   10167,   11191,    8034,   11191,   10585,
    5888,    5478,    4114,    2513,    4191,    4017,    2691,    4116,    3244,    3679,
    4585,    3091,    4714,    3889,    2951,    1830,    1115,     739,    1426,    2577,
       0,     994,    2695,     740,    3031,    2318,     993,    1616,    2227,    2173,
    1780,    5870,    5502,    5198,    5043,    4084,    4206,    4005,    3306,    4187,
    4575,    4868,    5894,    5658,    5165,    4962,    4671,    4246,    6207,    5550,
    5658,    5240,    4865,    5701,    5969,    5294,    4920,    3722,    6817,    6445,
    6410,    6289,    5827,    7110,    6918,    6571,    6184,    7901,    6407,    7066,
    7018,    6127,    6969,    7471,    7359,    7988,    8677,    7436,    7225,    6901,
    6745,    8034,    7826,    7804,    8084,    7942,    8541,    9112,    8397,    8854,
    8210,    8286,    8521,    9014,    9488,    9168,    9175,    8862,   10533,   10590,
   10570,   11129,   11614,   10879,   10823,   13407,   10891,    9708,   10131,   10650,
   12463,   11956,   13936,   13879,    6460,    7690,    6935,    8022,    8751,    8616,
    7877,    8260,    8183,    8834,    8609,    9016,    5999,    9632,    9057,    6407,
    5997,    4605,    3004,    4682,    4536,    3210,    5464,    3763,    4419,    5106,
    3612,    5235,    4410,    3442,    1653,    1441,    1034,    1105,    2201,     994,
       0,    1948,    1064,    2000,    1295,    1655,    2137,    2748,    1262,    1106,
    6391,    6023,    5719,    5564,    4605,    4727,    4526,    3827,    4708,    5096,
    5389,    6415,    6179,    5686,    5483,    5192,    4767,    6728,    6071,    6179,
    5761,    5386,    6222,    6490,    5815,    5441,    4243,    7338,    6966,    6931,
    6686,    6348,    7631,    7439,    7092,    6705,    8422,    6496,    7587,    7400,
    6216,    7115,    7992,    7809,    8509,    9198,    7607,    7306,    6806,    7266,
    8291,    8068,    7480,    8341,    7828,    9062,    9633,    8607,    8837,    8176,
    8096,    8218,    8778,   10009,    9479,    9000,    8836,   10503,   10433,   10195,
   11175,   11438,   10752,   10465,   12711,   11292,    9526,    9773,   10993,   12451,
   11944,   13430,   12919,    6917,    8186,    7456,    8543,    9247,    8748,    8005,
    8756,    8223,    9249,    8649,    9673,    6516,    9673,    9067,    8004,    7594,
    6342,    5030,    6348,    6133,    4807,    6232,    5360,    5795,    6475,    4981,
    6604,    5779,    5005,    2239,    2633,    2226,    2000,    1060,    2695,    1948,
       0,    2847,     858,    1555,    3249,    3506,    4117,    1157,    1092,    7760,
    7392,    7088,    6933,    5974,    6096,    5895,    5196,    6077,    6465,    6758,
    7784,    7548,    7055,    6852,    6561,    6136,    8097,    7440,    7548,    7130,
    6582,    7591,    7859,    6919,    6971,    5612,    8707,    8335,    8300,    7656,
    7369,    9000,    8808,    8461,    8074,    9791,    7466,    8740,    8370,    7186,
    8085,    8977,    8779,    9604,   10567,    8577,    8276,    7776,    8386,    9261,
    9038,    8450,    9311,    8798,   10228,   11002,    9577,    9807,    9146,    9066,
    9188,    9748,   11378,   10449,    9970,    9806,   11473,   11403,   11165,   12145,
   12408,   11722,   11435,   13681,   12262,   10496,   10743,   11963,   13421,   12914,
   14400,   13889,    7887,    8895,    8140,    9227,    9956,    9718,    8975,    9465,
    9193,   10219,    9619,   10643,    7486,   10643,   10037,    6230,    5820,    4568,
    3265,    4574,    4359,    3033,    4491,    3586,    3446,    4133,    2639,    4262,
    3437,    3324,    2401,    1681,    1468,    1997,    3048,     740,    1064,    2847,
       0,    2562,    1857,    1252,    1164,    1775,    1798,    1826,    5418,    5050,
    4746,    4591,    3632,    3754,    3553,    2854,    3735,    4123,    4416,    5442,
    5206,    4713,    4510,    4219,    3794,    5755,    5098,    5206,    4788,    4413,
    5249,    5517,    4842,    4468,    3270,    6365,    5993,    5958,    5837,    5375,
    6658,    6466,    6119,    5732,    7449,    5955,    6614,    6566,    5675,    6517,
    7019,    6907,    7536,    8225,    6984,    6773,    6449,    6293,    7582,    7374,
    7352,    7632,    7490,    8089,    8660,    7945,    8402,    7758,    7834,    8069,
    8562,    9036,    8716,    8723,    8410,   10081,   10138,   10118,   10677,   11162,
   10427,   10371,   12955,   10439,    9256,    9679,   10198,   12011,   11504,   13484,
   13452,    6008,    7238,    6483,    7570,    8299,    8164,    7425,    7808,    7731,
    8382,    8157,    8564,    5547,    9180,    8605,    8525,    8121,    6642,    5041,
    6719,    6777,    5513,    7747,    6089,    7292,    7004,    6472,    7818,    6603,
    5479,    3434,    3699,    3478,    2806,    1299,    2917,    2041,     811,    2942,
       0,    1314,    3948,    3273,    7328,    1435,    1743,    9563,    8992,    9057,
    8241,    6733,    5935,    6978,    7228,    7126,    7543,    8453,    9055,    8592,
    8202,    7956,    7730,    5975,    9088,    9122,    8696,    8105,    6341,    8439,
    9148,    6678,    6100,    7225,    9678,    9462,    9199,    7415,    7128,    9992,
    9857,    9598,    9168,   10670,    7225,    8499,    8129,    6945,    7844,    8736,
    8538,    9363,   11411,    8336,    8035,    7535,    8145,    9020,    8797,    8209,
    9070,    8557,    9987,   12159,    9336,    9566,    8905,    8825,    8947,    9507,
   11357,   10208,    9729,    9565,   11232,   11162,   10924,   11904,   12167,   11481,
   11194,   13440,   12021,   10255,   10502,   11722,   13180,   12673,   14159,   13648,
    7646,    8915,    8240,    9370,    9976,    9477,    8734,    9485,    8952,    9978,
    9378,   10402,    7245,   10402,    9796,    7663,    7259,    5780,    4179,    5857,
    5915,    4651,    7199,    5227,    6744,    6456,    5610,    7270,    6055,    4617,
    2779,    2835,    2622,    2261,    1611,    2369,    1526,    1429,    2394,    1543,
       0,    3086,    2725,    6780,     920,     520,    9015,    8444,    8509,    7693,
    6185,    5387,    6430,    6680,    6578,    6995,    7905,    8507,    8044,    7654,
    7408,    7182,    5427,    8540,    8574,    8148,    7557,    5793,    7891,    8600,
    6130,    5700,    6677,    9130,    8914,    8651,    6867,    6580,    9444,    9309,
    9050,    8620,   10122,    6677,    7951,    7581,    6397,    7296,    8188,    7990,
    8815,   10863,    7788,    7487,    6987,    7597,    8472,    8249,    7661,    8522,
    8009,    9439,   11611,    8788,    9018,    8357,    8277,    8399,    8959,   10809,
    9660,    9181,    9017,   10684,   10614,   10376,   11356,   11619,   10933,   10646,
   12892,   11473,    9707,    9954,   11174,   12632,   12125,   13611,   13100,    7098,
    8367,    7692,    8822,    9428,    8929,    8186,    8937,    8404,    9430,    8830,
    9854,    6697,    9854,    9248,    4977,    4567,    3315,    1920,    3321,    3106,
    1780,    3205,    2333,    2768,    3942,    2607,    4211,    3631,    2071,    1965,
     917,    1032,    1561,    3083,     993,    1655,    3249,    1251,    3662,    2949,
       0,    1851,    2672,    2829,    2277,    5773,    5947,    5643,    5488,    4529,
    4651,    4450,    3751,    4632,    5020,    5313,    6339,    6103,    5610,    5407,
    5116,    4691,    6652,    5995,    6103,    5685,    5310,    6146,    6414,    5739,
    5365,    4167,    7262,    6890,    6855,    6734,    6272,    7555,    7363,    7016,
    6629,    8346,    6852,    7511,    7463,    6572,    7414,    7916,    7804,    8433,
    9122,    7881,    7670,    7346,    7190,    8479,    8271,    8249,    8529,    8387,
    8986,    9557,    8842,    9299,    8655,    8731,    8966,    9459,    9933,    9613,
    9620,    9307,   10978,   11035,   11015,   11574,   12059,   11324,   11268,   13532,
   11336,   10153,   10576,   11095,   12908,   12401,   14251,   13764,    6905,    8135,
    7380,    8467,    9196,    9061,    8322,    8705,    8628,    9279,    9054,    9461,
    6444,   10077,    9502,    6841,    6431,    5179,    3677,    5185,    3286,    3223,
    3471,    2780,    2281,    3113,    1474,    3242,    2417,    3935,    3210,    2490,
    2277,    2806,    4062,    1616,    2137,    3506,    1164,    3273,    2725,    2061,
       0,     610,    2471,    2899,    4398,    4030,    3726,    3571,    2612,    2734,
    2533,    1834,    2715,    3103,    3396,    4422,    4186,    3693,    3490,    3199,
    2774,    4735,    4078,    4186,    3768,    3393,    4229,    4497,    3822,    3448,
    2250,    5345,    4973,    4938,    4817,    4355,    5638,    5446,    5099,    4712,
    6429,    4935,    5594,    5546,    4655,    5497,    5999,    5887,    6516,    7205,
    5964,    5753,    5429,    5273,    6562,    6354,    6332,    6612,    6470,    7069,
    7640,    6925,    7382,    6738,    6814,    7049,    7542,    8016,    7696,    7703,
    7390,    9061,    9118,    9098,    9657,   10142,    9407,    9351,   11935,    9419,
    8236,    8659,    9178,   10991,   10484,   12464,   12432,    4988,    6218,    5463,
    6550,    7279,    7144,    6405,    6788,    6711,    7362,    7137,    7544,    4527,
    8160,    7585,    6379,    5969,    4717,    3870,    4723,    2824,    2761,    2916,
    2318,    1819,    2484,    1012,    2687,    1850,    3473,    3821,    3101,    2888,
    3417,    4833,    2227,    2748,    4117,    1775,    3898,    3489,    2652,     610,
       0,    3082,    3510,    3899,    3531,    3227,    2820,    2057,    2710,    2034,
    1457,    2216,    2604,    2897,    3923,    3687,    3194,    2991,    2700,    2654,
    4230,    3579,    3687,    3269,    3369,    3730,    3998,    3635,    3424,    1873,
    4738,    4474,    4439,    4318,    3856,    5134,    4947,    4600,    4213,    5730,
    4882,    5095,    5047,    4602,    5440,    5500,    5388,    6017,    6471,    5819,
    5700,    5376,    5313,    6063,    6209,    6372,    6113,    6510,    6570,    7141,
    6426,    6883,    6593,    7048,    6117,    7043,    7517,    7197,    7858,    7376,
    8438,    8619,    8581,    9121,    9384,    8698,    9482,   10715,    9447,    7737,
    8790,    8679,   10397,    9890,   11434,   10947,    5028,    6258,    5503,    6590,
    7319,    7184,    6445,    6828,    6751,    7402,    7177,    7584,    4567,    8200,
    7625,    7785,    7381,    5902,    4301,    5979,    6037,    4610,    5798,    5252,
    4753,    5440,    3946,    5569,    4744,    4739,    2855,    2758,    2351,    2277,
    1692,    2164,    1301,    1157,    1798,     737,     972,    2829,    2471,    3082,
       0,    1043,    6725,    6357,    6053,    5898,    4939,    5061,    4860,    4161,
    5042,    5430,    5723,    6749,    6513,    6020,    5817,    5526,    5101,    7062,
    6405,    6513,    6095,    5588,    6556,    6824,    5925,    5936,    4577,    7672,
    7300,    7265,    6662,    6375,    7965,    7773,    7426,    7039,    8756,    6472,
    7746,    7376,    6192,    7091,    7983,    7785,    8610,    9532,    7583,    7282,
    6782,    7392,    8267,    8044,    7456,    8317,    7804,    9234,    9967,    8583,
    8813,    8152,    8072,    8194,    8754,   10343,    9455,    8976,    8812,   10479,
   10409,   10171,   11151,   11414,   10728,   10441,   12687,   11268,    9502,    9749,
   10969,   12427,   11920,   13406,   12895,    6893,    7860,    7105,    8192,    8921,
    8724,    7981,    8430,    8199,    9225,    8625,    9649,    6492,    9649,    9043,
    7029,    6619,    5259,    3658,    5336,    5158,    3832,    5257,    4385,    4820,
    5868,    4374,    5997,    5172,    4096,    2077,    2067,    1660,    1504,    1149,
    1780,    1106,    1092,    1826,    1851,     569,    2277,    2899,    3510,    1043,
       0,    7153,    6785,    6481,    6326,    5367,    5489,    5288,    4589,    5470,
    5858,    6151,    7177,    6941,    6448,    6245,    5954,    5529,    7490,    6833,
    6941,    6523,    5986,    6984,    7252,    6323,    6464,    5005,    8100,    7728,
    7693,    7060,    6773,    8393,    8201,    7854,    7467,    9184,    6870,    8144,
    7774,    6590,    7489,    8381,    8183,    9008,    9960,    7981,    7680,    7180,
    7790,    8665,    8442,    7854,    8715,    8202,    9632,   10395,    8981,    9211,
    8550,    8470,    8592,    9152,   10771,    9853,    9374,    9210,   10877,   10807,
   10569,   11549,   11812,   11126,   10839,   13085,   11666,    9900,   10147,   11367,
   12825,   12318,   13804,   13293,    7291,    8388,    7633,    8720,    9449,    9122,
    8379,    8958,    8597,    9623,    9023,   10047,    6890,   10047,    9441,    5671,
    5262,    4412,    5848,    2466,    3130,    4060,    2772,    3507,    3150,    1982,
    3239,    1393,    2149,    4445,    7370,    6660,    6461,    7048,    8267,    5808,
    6391,    7752,    5418,    7332,    6923,    5773,    4398,    3899,    6594,    7123,
       0,     837,     945,     830,    1641,    3371,    2065,    2730,    2503,    1967,
    1548,     972,    1292,    1587,    1977,    2623,    2942,    1513,    2082,    1657,
    2627,    3004,    2778,    2489,    3228,    3581,    2962,    1906,    2390,    2818,
    3354,    3295,    2506,    2597,    2338,    1970,    2904,    3681,    2923,    3153,
    3761,    3696,    3289,    3494,    3564,    3645,    3917,    4068,    4011,    5026,
    3914,    4315,    4647,    4160,    4785,    4342,    4393,    4230,    4869,    4691,
    5154,    5546,    4998,    5065,    4959,    6043,    5482,    5612,    6200,    6415,
    6218,    6558,    5872,    7588,    7889,    7553,    5746,    6896,    6141,    7552,
    7045,    8608,    8121,    5174,    6750,    6022,    6924,    7496,    6529,    6207,
    7349,    8079,    7194,    8505,    8073,    4870,    8830,    7569,    6309,    5900,
    5050,    5010,    3104,    2956,    3886,    2598,    3333,    2892,    1808,    2981,
    1215,    1891,    5083,    6532,    5822,    5623,    6210,    7429,    4970,    5758,
    6914,    4589,    6494,    6085,    5248,    4030,    3303,    5756,    6285,     841,
       0,     362,     572,    1319,    2635,    1508,    2254,    1946,    1410,    1027,
     493,     546,    1025,    1456,    1953,    2272,     956,    1561,    1136,    2088,
    2483,    2257,    1968,    2680,    3060,    2396,    1498,    1789,    2255,    2713,
    2774,    1860,    1811,    1552,    1420,    2490,    3160,    2252,    2564,    3240,
    3164,    2582,    2973,    2918,    3231,    3131,    3547,    3490,    4505,    3268,
    3592,    4126,    3425,    4264,    3928,    3979,    3584,    4223,    3905,    4633,
    4760,    4352,    4676,    4545,    5522,    4961,    5198,    5786,    5769,    5829,
    6144,    5458,    7067,    7475,    7032,    5100,    6375,    5752,    7157,    6650,
    8194,    7707,    4653,    6163,    5488,    6376,    6975,    6008,    5686,    6733,
    7306,    6662,    7732,    7552,    4349,    8237,    6783,    6413,    6004,    5154,
    5272,    3208,    3247,    4197,    3059,    3598,    2987,    2099,    3076,    1407,
    2005,    5187,    6782,    6072,    5859,    6388,    7679,    5198,    5719,    7088,
    4746,    6744,    6335,    5498,    3726,    3227,    6006,    6481,     945,     424,
       0,     885,    1316,    2272,    1176,    1891,    1590,    1106,     639,     716,
     469,     662,    1068,    1565,    1884,     965,    1157,     732,    1718,    2095,
    1853,    1564,    2317,    2672,    2033,    1555,    1465,    1892,    2350,    2386,
    1869,    1734,    1475,    1045,    2547,    2756,    1998,    2228,    2887,    2745,
    2403,    2569,    2860,    3288,    3000,    3143,    3074,    4101,    3244,    3390,
    3722,    3294,    3860,    3751,    4036,    3593,    4064,    3774,    4229,    4347,
    4224,    4698,    4378,    5118,    4557,    5255,    5800,    5778,    5938,    6201,
    5515,    6663,    7532,    6628,    4918,    5971,    5838,    7214,    6707,    8251,
    7764,    4249,    5800,    5125,    5963,    6571,    5604,    5282,    6370,    6943,
    6269,    7369,    7148,    3961,    7874,    6370,    6298,    5889,    4296,    4763,
    3093,    2475,    3405,    2117,    2852,    2350,    1327,    2439,     734,    1349,
    4253,    6285,    5575,    5376,    5963,    7182,    4723,    5511,    6667,    4342,
    6247,    5838,    5001,    3571,    3056,    5509,    6038,     830,     572,     885,
       0,     825,    2570,    1264,    1903,    1702,    1166,     804,    1062,    1076,
    1231,    1237,    1822,    2141,    1486,    1726,    1597,    2048,    2425,    2292,
    2133,    2649,    3002,    2135,    1994,    2319,    2462,    2689,    2716,    2390,
    2341,    2082,    1910,    2986,    3325,    2782,    2859,    3182,    3330,    3112,
    3200,    3448,    3727,    3631,    3770,    3655,    4728,    3798,    4021,    4333,
    3925,    4471,    4382,    4475,    4114,    4695,    4405,    4860,    4932,    4855,
    5329,    5009,    5748,    5188,    5694,    6282,    6299,    6377,    6640,    5954,
    7294,    7971,    7259,    5549,    6602,    6277,    7653,    7146,    8690,    8203,
    4680,    6198,    5443,    6548,    7194,    6235,    5893,    6768,    7500,    6886,
    7926,    7775,    4291,    8459,    6955,    6132,    5722,    4261,    3759,    3584,
    2213,    2894,    1757,    2296,    1657,    1369,    1741,    1153,     703,    3778,
    5281,    4571,    4372,    4959,    6178,    3719,    4507,    5663,    3338,    5243,
    4834,    3997,    2612,    2052,    4505,    5034,    1641,    1319,    1316,     825,
       0,    1761,     973,    1104,    1155,    1443,    1023,    2012,    1776,    1508,
    1448,    1639,    1440,    2325,    1827,    1776,    2098,    2350,    2342,    2410,
    2574,    2691,    1336,    2935,    2563,    2739,    2900,    2766,    3228,    3036,
    2689,    2302,    4019,    3602,    3184,    3136,    3232,    3675,    3589,    3477,
    4106,    4795,    3908,    4047,    3932,    4465,    4152,    4298,    4626,    4202,
    4513,    4659,    5230,    4515,    4972,    4682,    5137,    4903,    5132,    5606,
    5286,    6026,    5465,    6651,    6708,    6688,    7247,    7732,    6997,    7571,
    9525,    7536,    5826,    6879,    6768,    8581,    8074,   10054,    9986,    4463,
    5501,    4826,    5956,    6562,    6294,    5551,    6071,    6644,    6795,    7070,
    7008,    3831,    7575,    6613,    7121,    6717,    5287,    4586,    5214,    3382,
    3721,    2926,    3143,    2484,    2196,    2568,    2697,    1795,    4654,    5800,
    5080,    4867,    5396,    6795,    4206,    4727,    6096,    3754,    5872,    5451,
    4651,    2734,    2710,    5061,    5489,    3371,    2814,    2302,    2570,    2023,
       0,    1306,    1324,     901,    1384,    1703,    2927,    2256,    1637,    1177,
     790,     414,    2633,    1909,    1993,    1280,     746,    1541,    2162,    1083,
     901,     996,    3369,    2678,    2351,    2168,    1726,    3498,    3139,    2914,
    2474,    4143,    2111,    3385,    2926,    1831,    2730,    3622,    3398,    4182,
    4700,    3222,    2921,    2421,    2579,    3906,    3660,    3095,    3956,    3006,
    4580,    5151,    4222,    4452,    3791,    3711,    3396,    4393,    5527,    5094,
    4510,    4451,    6118,    6048,    5810,    6790,    7053,    6367,    5662,    8326,
    6725,    5141,    4970,    6608,    8066,    7559,    9045,    8534,    2809,    3994,
    3319,    4449,    5055,    4787,    4044,    4564,    5137,    5183,    5563,    5485,
    2232,    6068,    5106,    6251,    5841,    4380,    4149,    4328,    2332,    3014,
    1876,    2415,    1804,    1518,    1893,    1632,     822,    3897,    5599,    4879,
    4666,    5195,    6556,    4005,    4526,    5895,    3553,    5621,    5212,    4375,
    2533,    2034,    4860,    5288,    2065,    1508,    1204,    1264,     973,    1306,
       0,     767,     438,     568,     863,    1900,    1614,    1160,     957,     755,
     987,    2110,    1545,    1665,    1130,    1337,    1464,    1964,    1561,    1974,
     910,    2700,    2452,    2224,    2273,    1795,    3014,    2879,    2578,    2190,
    3692,    2541,    3073,    2799,    2261,    3077,    3478,    3366,    3995,    4433,
    3480,    3390,    3066,    3494,    3990,    3941,    4003,    4040,    4141,    4548,
    5119,    4306,    4861,    4254,    4696,    4666,    4801,    5495,    5175,    5495,
    5354,    6400,    6456,    6218,    7083,    7346,    6660,    7143,    8677,    7425,
    5549,    6451,    6657,    8359,    7852,    9396,    8909,    3832,    5017,    4342,
    5472,    6078,    5810,    5067,    5587,    6160,    6311,    6586,    6524,    3335,
    7091,    6129,    6382,    5972,    4511,    4007,    4724,    2463,    3142,    2007,
    2546,    1905,    1617,    1707,    1778,     953,    4028,    4900,    4180,    3967,
    4496,    6414,    3306,    3827,    5196,    2854,    5479,    5070,    3751,    1834,
    1457,    4161,    4589,    2730,    2362,    2058,    1903,    1104,    1324,     736,
       0,     846,    1301,    1630,    2754,    2350,    1927,    1714,    1433,    1081,
    2846,    2312,    2454,    1863,    1757,    2197,    2731,    2294,    2038,     440,
    3436,    3220,    2957,    3006,    2564,    3750,    3615,    3356,    2926,    4428,
    3305,    3926,    3532,    3025,    3810,    4331,    4219,    4808,    5169,    4213,
    4123,    3799,    3903,    4723,    4674,    4797,    4773,    4154,    5401,    5917,
    5039,    5648,    4987,    5429,    4544,    5534,    6348,    6028,    6228,    6169,
    7136,    7189,    6951,    7819,    8082,    7396,    6810,    9413,    8278,    6282,
    6118,    7510,    9095,    8588,   10132,    9645,    3830,    5142,    4467,    5597,
    6203,    5935,    5192,    5712,    6285,    6204,    6711,    6622,    3369,    7216,
    6254,    6433,    6023,    4562,    4063,    4332,    2514,    3196,    2058,    2597,
    1961,    1673,    2045,    1829,    1004,    4079,    5573,    4863,    4664,    5251,
    6470,    4011,    4708,    5955,    3630,    5535,    5126,    4289,    2715,    2216,
    4797,    5326,    2503,    1946,    1642,    1702,    1155,     888,     438,     857,
       0,     502,     881,    2292,    1773,    1154,     915,     569,     567,    2277,
    1539,    1655,    1064,    1230,    1398,    2074,    1495,    1569,     473,    2893,
    2421,    2158,    2187,    1725,    3185,    2928,    2581,    2127,    3885,    2471,
    3076,    2733,    2191,    3011,    3481,    3369,    3998,    4620,    3414,    3324,
    3000,    3256,    3924,    3875,    3933,    3974,    4071,    4551,    5122,    4240,
    4849,    4188,    4415,    4596,    4735,    5498,    5178,    5304,    4991,    6460,
    6390,    6152,    7132,    7395,    6547,    6952,    8611,    7020,    5483,    6260,
    6660,    8408,    7901,    9387,    8876,    3486,    4628,    3953,    5083,    5689,
    5421,    4678,    5198,    5771,    5860,    6197,    6135,    2958,    6702,    5740,
    6821,    6411,    4950,    4633,    3830,    2902,    3584,    2446,    2985,    2374,
    2088,    2463,    1534,    1392,    4467,    6143,    5433,    5234,    5765,    7040,
    4575,    5096,    6465,    4123,    6105,    5696,    4859,    3103,    2604,    5367,
    5858,    1967,    1410,    1106,    1166,    1443,    1387,     537,    1252,     502,
       0,     379,    1574,    1259,     640,     413,     650,     969,    1763,    1025,
    1154,     908,    1285,    1152,    1444,    1509,    1862,     976,    2391,    1941,
    1834,    1900,    1576,    2683,    2414,    2067,    1654,    3383,    2322,    2562,
    2409,    2042,    2687,    2967,    2855,    3484,    4106,    3090,    3205,    2881,
    3275,    3530,    3551,    3690,    3580,    3828,    4037,    4608,    3865,    4350,
    3864,    4306,    4289,    4411,    4984,    4664,    5105,    4843,    6091,    6066,
    5828,    6774,    7037,    6033,    6753,    8097,    6914,    5159,    6061,    6146,
    8050,    7543,    9087,    8600,    3540,    5044,    4303,    5390,    6105,    5837,
    5034,    5614,    6187,    6192,    6613,    6404,    3151,    7118,    6156,    6737,
    6333,    4886,    4755,    3517,    3147,    3877,    2621,    3278,    2653,    1726,
    2737,    1140,    1685,    4760,    6277,    5567,    5368,    5955,    7174,    4715,
    5389,    6659,    4334,    6239,    5830,    4993,    3396,    2897,    5501,    6030,
    1548,    1027,     639,     804,    1023,    1648,     857,    1572,     881,     379,
       0,    1261,     873,     270,     469,     966,    1285,    1424,     684,     784,
    1101,    1496,    1363,    1103,    1693,    2073,    1355,    2130,    1571,    1447,
    1908,    1787,    2403,    2044,    1697,    1284,    3196,    2295,    2192,    2144,
    2253,    2222,    2597,    2485,    3114,    3736,    2873,    2601,    2625,    3486,
    3160,    3306,    3180,    3210,    3318,    3667,    4238,    3523,    3980,    3647,
    4089,    4072,    4140,    4614,    4294,    4888,    4473,    5846,    5716,    5611,
    6442,    6850,    5663,    6536,    7727,    6544,    4834,    5844,    5776,    7776,
    7269,    8900,    8413,    3751,    5176,    4501,    5601,    6029,    5520,    4740,
    5746,    6319,    6026,    6745,    6606,    3362,    7250,    6095,    6644,    6235,
    5385,    5504,    3439,    3446,    4376,    3088,    4092,    3402,    2298,    3486,
    1705,    2701,    5418,    7026,    6316,    6117,    6704,    7923,    5464,    6252,
    7408,    5083,    6988,    6579,    5742,    4422,    3797,    6250,    6779,     972,
     493,     716,    1062,    2012,    2935,    1900,    2748,    2338,    1574,    1261,
       0,     615,    1190,    1701,    2198,    2517,     841,    1685,    1131,    2221,
    2678,    2381,    2040,    2902,    3255,    2890,    1024,    1928,    2439,    2894,
    2889,    1859,    1968,    1691,    1444,    2108,    3304,    2432,    2691,    3559,
    3234,    2502,    3032,    2829,    2884,    3410,    3606,    3652,    4564,    3179,
    3853,    4185,    3429,    4323,    3523,    3604,    3588,    4143,    4184,    4692,
    5039,    4189,    4183,    4147,    5281,    4787,    4740,    5484,    5873,    5336,
    5821,    5086,    6893,    7382,    6941,    5011,    6201,    5259,    6670,    6163,
    8101,    7614,    4815,    6288,    5737,    6462,    7034,    5834,    5745,    6887,
    7584,    6499,    8010,    7611,    4544,    8368,    7062,    6760,    6351,    5501,
    5514,    3555,    3594,    4657,    3299,    4058,    3412,    2446,    3496,    1867,
    2465,    5534,    7036,    6326,    6127,    6714,    7933,    5474,    6179,    7418,
    5093,    6998,    6589,    5752,    4186,    3687,    6260,    6789,    1212,     546,
     480,    1081,    1776,    2229,    1636,    2351,    1773,    1259,     873,     615,
       0,     619,    1130,    1611,    1946,     545,    1114,     560,    1650,    2077,
    1810,    1469,    2274,    2684,    2247,    1157,    1242,    1753,    2211,    2318,
    1449,    1264,    1005,     873,    2149,    2669,    1705,    2017,    2810,    2599,
    2035,    2397,    2507,    2890,    2584,    2971,    2945,    3929,    2828,    3045,
    3550,    2878,    3688,    3579,    3638,    3144,    3783,    3358,    4057,    4213,
    3913,    4413,    4204,    4946,    4385,    4857,    5445,    5330,    5540,    5803,
    5117,    6491,    7134,    6456,    4661,    5799,    5440,    6816,    6309,    7853,
    7366,    4180,    5653,    5059,    5827,    6399,    5432,    5110,    6252,    6887,
    6097,    7313,    6976,    3973,    7733,    6236,    7033,    6629,    5199,    5051,
    3813,    3443,    4174,    2917,    3575,    2949,    2121,    3033,    1534,    1982,
    5057,    6573,    5863,    5664,    6251,    7470,    5011,    5686,    6955,    4630,
    6535,    6126,    5289,    3693,    3194,    5797,    6326,    1587,    1066,     662,
    1231,    1508,    1610,    1153,    1868,    1154,     640,     270,    1190,     619,
       0,     511,     992,    1327,    1120,     482,     514,    1031,    1458,    1191,
     901,    1655,    2065,    1628,    1732,    1301,    1230,    1688,    1699,    2024,
    1774,    1427,    1007,    2724,    2093,    1922,    1805,    2165,    2083,    2327,
    2215,    2844,    3465,    2486,    2655,    2412,    3321,    2890,    2947,    3086,
    2940,    3224,    3397,    3968,    3206,    3710,    3260,    3702,    3685,    3807,
    4344,    4024,    4501,    4203,    5432,    5446,    5224,    6115,    6378,    5393,
    6149,    7457,    6274,    4555,    5457,    5506,    7391,    6884,    8428,    7941,
    3586,    5138,    4463,    5301,    5947,    5250,    4646,    5708,    6281,    5639,
    6707,    6645,    3354,    7212,    5708,    7400,    6996,    5337,    5030,    4180,
    3289,    3971,    2833,    3372,    2761,    2151,    2850,    1565,    1779,    4854,
    6540,    5830,    5623,    6152,    7437,    4962,    5483,    6852,    4510,    6502,
    6093,    5256,    3490,    2991,    5764,    6245,    1977,    1456,    1068,    1237,
    1448,    1177,     934,    1649,     926,     413,     469,    1701,    1109,     490,
       0,     440,     762,    1610,     747,     855,     631,    1026,     893,    1166,
    1223,    1603,    1400,    2222,    1621,    1362,    1438,    1317,    2415,    2106,
    1759,    1327,    3077,    2063,    2254,    1937,    1783,    2215,    2659,    2547,
    3176,    3798,    2618,    2690,    2385,    3016,    3128,    3079,    3218,    3178,
    3356,    3729,    4300,    3444,    4042,    3392,    3681,    3817,    3939,    4676,
    4356,    4570,    4535,    5548,    5594,    5356,    6144,    6599,    5725,    6218,
    7789,    6606,    4687,    5526,    5838,    7478,    6971,    8591,    8080,    3281,
    4706,    4031,    5131,    5767,    5181,    4756,    5276,    5849,    5771,    6275,
    6145,    2892,    6780,    5818,    6917,    6507,    5046,    4602,    4480,    2998,
    3680,    2542,    3081,    2470,    2184,    2559,    2190,    1488,    4563,    6112,
    5402,    5203,    5790,    7009,    4550,    5192,    6494,    4169,    6074,    5665,
    4828,    3199,    2700,    5336,    5865,    2623,    1953,    1565,    1822,    1639,
     790,     609,    1324,     538,     650,     966,    2193,    1522,     903,     440,
       0,     397,    1895,    1135,    1255,     569,     711,     884,    1505,     935,
    1288,    1012,    2635,    2021,    1694,    1618,    1156,    2828,    2494,    2147,
    1734,    3461,    1902,    2632,    2241,    1622,    2529,    3037,    2757,    3554,
    4176,    2953,    2785,    2461,    2855,    3432,    3386,    3364,    3482,    3502,
    3939,    4510,    3779,    4388,    3727,    3846,    4027,    4274,    4886,    4566,
    4735,    4422,    5758,    5929,    5691,    6354,    6839,    5935,    6383,    7999,
    6451,    5022,    5691,    6048,    7688,    7181,    8926,    8321,    3074,    4484,
    3729,    4816,    5551,    5283,    4540,    5054,    5633,    5772,    6059,    5830,
    2577,    6564,    5602,    6982,    6572,    5111,    4921,    4799,    3063,    3745,
    2607,    3146,    2535,    2249,    2624,    2378,    1553,    4628,    5840,    5120,
    4907,    5436,    7328,    4246,    4767,    6136,    3794,    6393,    5984,    4691,
    2774,    2750,    5101,    5529,    2942,    2272,    1884,    2141,    1704,     414,
     928,    1109,     582,     969,    1285,    2512,    1841,    1222,     762,     397,
       0,    2342,    1479,    1587,     922,     743,    1256,    1902,    1155,    1082,
     708,    2954,    2353,    2016,    2015,    1553,    3147,    2838,    2491,    2059,
    3780,    2364,    2986,    2591,    2084,    2869,    3391,    3444,    3908,    4519,
    3272,    3182,    2858,    2769,    3782,    3733,    3828,    3832,    3966,    4770,
    5267,    4098,    4707,    4046,    4310,    4471,    4593,    5717,    5165,    5199,
    4886,    6318,    6248,    6010,    6990,    7253,    6567,    6847,    8526,    6915,
    5341,    6155,    6808,    8266,    7759,    9245,    8734,    2999,    4409,    3654,
    4741,    5694,    5155,    4416,    4979,    5711,    5373,    6137,    5755,    2502,
    6512,    5596,    7309,    6900,    5991,    5924,    4104,    4143,    5090,    3709,
    4512,    3822,    2995,    3906,    2416,    3014,    5997,    7446,    6736,    6537,
    7124,    8343,    5884,    6672,    7828,    5503,    7408,    6999,    6162,    4735,
    4217,    6670,    7199,    1513,     956,    1029,    1491,    2325,    2633,    2204,
    2919,    2277,    1763,    1424,     841,     548,    1123,    1634,    1895,    2450,
       0,     921,     666,    1442,    2027,    1652,    1299,    2034,    2518,    2751,
     666,     968,    1479,    1934,    2032,     904,     995,     731,     604,    1621,
    2344,    1436,    1731,    2541,    2274,    1687,    2072,    1962,    2362,    2315,
    2646,    2676,    3604,    2312,    2776,    3225,    2558,    3363,    3059,    3110,
    2628,    3267,    3089,    3732,    3944,    3396,    3811,    3676,    4621,    4044,
    4329,    4917,    4813,    4964,    5275,    4589,    6129,    6606,    6131,    4144,
    5437,    4887,    6288,    5781,    7325,    6838,    3855,    5328,    4777,    5502,
    6074,    5107,    4785,    5927,    6618,    5772,    7044,    6651,    3691,    7408,
    5967,    7422,    7018,    5588,    5440,    4202,    3832,    4559,    3306,    3960,
    3338,    2510,    3422,    1923,    2367,    5442,    6962,    6252,    6053,    6640,
    7859,    5400,    6071,    7344,    5019,    6924,    6515,    5678,    4078,    3579,
    6186,    6715,    2082,    1561,    1157,    1697,    1827,    1845,    1545,    2312,
    1539,    1025,     684,    1685,    1114,     482,     747,    1125,    1479,     921,
       0,     540,     649,    1234,     810,     418,    1241,    1725,    2013,    1614,
     971,     762,    1283,    1273,    1882,    1432,    1176,     763,    2432,    1610,
    1582,    1354,    1811,    1537,    1987,    1875,    2504,    3126,    2092,    1916,
    1940,    2838,    2550,    2482,    2495,    2600,    2633,    3057,    3628,    2913,
    3370,    2866,    3321,    3312,    3372,    4004,    3684,    4165,    3710,    4876,
    5106,    4888,    5472,    5957,    5053,    5813,    7117,    5781,    4219,    5121,
    5166,    6806,    6299,    8123,    7439,    3103,    4598,    4025,    4772,    5344,
    4821,    4055,    5197,    5867,    5303,    6293,    5921,    2930,    6678,    5235,
    7125,    6716,    5702,    5554,    3920,    3760,    4657,    3420,    4058,    3447,
    2453,    3536,    1867,    2465,    5540,    7076,    6366,    6167,    6754,    7973,
    5514,    6179,    7458,    5133,    7038,    6629,    5792,    4186,    3687,    6300,
    6829,    1657,    1136,     732,    1597,    1776,    1993,    1656,    2371,    1668,
    1154,     784,    1131,     560,     514,     867,    1255,    1599,     666,     542,
       0,    1063,    1746,    1224,     949,    1696,    2139,    2142,    1377,     927,
    1278,    1814,    1731,    1671,    1312,     965,     538,    2339,    2141,    1460,
    1651,    2358,    2190,    1865,    1992,    2322,    3046,    2423,    2562,    2471,
    3520,    2667,    2813,    3141,    2717,    3279,    3174,    3511,    3030,    3487,
    3197,    3652,    4188,    3647,    4121,    3801,    4541,    3980,    5155,    5223,
    5203,    5751,    6236,    5501,    6086,    7653,    6051,    4341,    5394,    5283,
    7085,    6578,    8372,    7885,    3634,    5244,    4556,    5418,    5990,    5027,
    4701,    5843,    6540,    5692,    6966,    6567,    3344,    7324,    6211,    7486,
    7076,    5615,    5505,    4890,    3567,    4249,    3111,    3650,    3039,    2753,
    3128,    2215,    2057,    5132,    6834,    6114,    5901,    6430,    7912,    5240,
    5761,    7130,    4788,    6977,    6568,    5685,    3768,    3269,    6095,    6523,
    2627,    2106,    1718,    2048,    2098,    1280,    1452,    2002,    1138,     908,
    1119,    2221,    1650,    1031,     649,     569,     966,    1442,     649,    1063,
       0,     605,     333,     954,     591,    1096,    1642,    2135,    1470,    1093,
    1142,     700,    2290,    1931,    1706,    1276,    2857,    1441,    2081,    1668,
    1161,    1946,    2486,    2206,    3003,    3596,    2349,    2259,    1935,    2456,
    2859,    2810,    2949,    2909,    3087,    3388,    3959,    3175,    3701,    3123,
    3447,    3548,    3670,    4335,    4015,    4336,    4046,    5207,    5325,    5087,
    5803,    6288,    5384,    5984,    7448,    6117,    4418,    5292,    5497,    7137,
    6630,    8322,    7770,    2721,    4074,    3399,    4529,    5135,    4867,    4124,
    4644,    5217,    5368,    5643,    5554,    2301,    6148,    5186,    7628,    7218,
    5757,    5367,    5245,    3709,    4391,    3253,    3792,    3181,    2895,    3270,
    2592,    2199,    5274,    6459,    5739,    5526,    6055,    7399,    4865,    5386,
    6755,    4413,    6476,    6055,    5310,    3393,    3369,    5720,    6148,    3004,
    2483,    2095,    2425,    2350,     746,    1374,    1757,    1230,    1285,    1496,
    2678,    2107,    1488,    1026,     711,     743,    2027,    1234,    1704,     605,
       0,     841,    1462,     409,     587,    1356,    2720,    1978,    1651,    1484,
    1022,    2798,    2439,    2214,    1869,    3439,    1645,    2589,    2222,    1365,
    2207,    3119,    2802,    3586,    4177,    2674,    2463,    2139,    2587,    3467,
    3064,    2966,    3517,    2877,    3984,    4555,    3783,    4096,    3435,    3524,
    3267,    4037,    4931,    4611,    4381,    4100,    5762,    5681,    5400,    6399,
    6697,    5980,    5533,    7970,    6129,    4726,    4841,    6093,    7710,    7203,
    8689,    8178,    2448,    3858,    3103,    4190,    4926,    4658,    3915,    4428,
    5008,    5159,    5434,    5204,    1951,    5939,    4977,    7947,    7537,    6076,
    5486,    4897,    4028,    4621,    3572,    4043,    3384,    3205,    3468,    2459,
    2518,    5593,    6996,    6286,    6087,    6674,    7893,    5434,    6222,    7378,
    5053,    6958,    6549,    5712,    4229,    3730,    6220,    6749,    2778,    2257,
    1853,    2292,    2342,    1480,    1493,    2208,    1422,    1152,    1363,    2381,
    1810,    1191,     893,     884,    1281,    1554,     763,    1224,     333,     841,
       0,     621,     646,    1357,    1896,    1820,    1137,     760,     836,     583,
    1957,    1598,    1373,     943,    2524,    1453,    1748,    1335,    1049,    1613,
    2153,    1873,    2670,    3263,    2016,    2088,    1783,    2282,    2526,    2477,
    2616,    2576,    2754,    3055,    3626,    2842,    3368,    2790,    3079,    3215,
    3337,    4002,    3682,    3968,    3713,    4874,    4992,    4754,    5470,    5955,
    5051,    5616,    7115,    5784,    4085,    4924,    5164,    6804,    6297,    7989,
    7437,    2547,    4041,    3286,    4373,    5195,    4579,    4041,    4611,    5277,
    5169,    5703,    5641,    2134,    6208,    5221,    7841,    7437,    6007,    5859,
    4621,    4251,    4978,    3725,    4379,    3757,    2929,    3841,    2342,    2786,
    5861,    7381,    6671,    6472,    7059,    8278,    5819,    6490,    7763,    5438,
    7343,    6934,    6097,    4497,    3998,    6605,    7134,    2489,    1968,    1564,
    2116,    2410,    2162,    1964,    2731,    2012,    1444,    1103,    2040,    1469,
     901,    1166,    1505,    1902,    1209,     418,     949,     954,    1462,     621,
       0,    1175,    1978,    2486,    1475,     515,     343,     781,    1115,    1335,
     976,     751,     590,    1976,    1191,    1126,     898,    1446,    1118,    1531,
    1419,    2048,    2670,    1636,    1497,    1521,    2419,    2094,    2026,    2076,
    2144,    2214,    2601,    3172,    2457,    2914,    2410,    2865,    2893,    2916,
    3548,    3228,    3754,    3254,    4420,    4650,    4554,    5016,    5501,    4597,
    5402,    6661,    5325,    3768,    4710,    4710,    6350,    5843,    7823,    6983,
    2684,    4179,    3606,    4353,    4925,    4365,    3636,    4778,    5650,    5030,
    6076,    5502,    2651,    6259,    4816,    7852,    7442,    5981,    5536,    5414,
    3933,    4615,    3477,    4016,    3405,    3119,    3494,    2816,    2423,    5498,
    6888,    6168,    5955,    6484,    7540,    5294,    5815,    7025,    4842,    6617,
    6196,    5739,    3822,    3635,    5879,    6396,    3228,    2707,    2319,    2649,
    2574,    1086,    1543,    2258,    1472,    1509,    1720,    2902,    2331,    1712,
    1250,     934,    1155,    2075,    1282,    1696,     653,     409,     624,    1175,
       0,     904,    1768,    2352,    1669,    1292,    1081,     639,    2511,    2152,
    1905,    1475,    3056,    1236,    2392,    1867,     956,    1798,    2710,    2393,
    3177,    3768,    2265,    2054,    1730,    2178,    3058,    2655,    2633,    3108,
    2771,    3575,    4146,    3374,    3700,    3039,    3115,    3350,    3635,    4522,
    4202,    4004,    3691,    5394,    5272,    4991,    5990,    6330,    5571,    5652,
    7603,    5720,    4317,    4960,    5684,    7324,    6817,    8322,    7811,    2145,
    3555,    2800,    3887,    5031,    4615,    3937,    4125,    4857,    5095,    5283,
    4901,    1648,    5658,    5082,    7969,    7559,    6098,    5500,    5844,    4050,
    4732,    3594,    4133,    3522,    3236,    3587,    3169,    2540,    5615,    6514,
    5794,    5581,    6110,    7100,    4920,    5441,    6971,    4468,    6100,    5700,
    5365,    3448,    3424,    5936,    6464,    3581,    3060,    2672,    3002,    2691,
     901,    1974,    2038,    1569,    1862,    2073,    3255,    2684,    2065,    1603,
    1288,    1082,    2518,    1725,    2139,    1096,     587,    1357,    1978,     904,
       0,    1861,    3565,    2494,    2167,    2004,    1542,    3314,    2955,    2730,
    2300,    4269,    2057,    3399,    2742,    1777,    2619,    3531,    3214,    3998,
    4589,    3086,    2875,    2551,    2395,    3889,    3476,    3454,    3939,    3592,
    4396,    4967,    4252,    4521,    3860,    3936,    4171,    4456,    5343,    5023,
    4825,    4512,    6215,    6093,    5812,    6811,    7296,    6392,    6473,    8456,
    6541,    5138,    5781,    6505,    8145,    7638,    9618,    8778,    2321,    3767,
    3012,    4099,    5016,    4477,    3738,    4337,    4831,    4695,    5257,    5113,
    1860,    5870,    4918,    6614,    6204,    4743,    4162,    4806,    2695,    3297,
    2239,    2719,    2060,    1772,    2123,    2010,    1185,    4230,    5316,    4596,
    4383,    4912,    6569,    3722,    4243,    5612,    3270,    5634,    5225,    4167,
    2250,    1873,    4577,    5005,    2962,    2464,    2290,    2135,    1336,    1029,
     935,     440,     473,     976,    1574,    2766,    2247,    1628,    1389,    1073,
     708,    2751,    2013,    2129,    1538,    1356,    1872,    2578,    1768,    1861,
       0,    3367,    2895,    2632,    2681,    2229,    3659,    3402,    3055,    2601,
    4359,    2980,    3550,    3207,    2700,    3485,    3955,    3843,    4472,    5094,
    3888,    3798,    3474,    3351,    4398,    4349,    3870,    4448,    3781,    5025,
    5596,    4714,    5323,    4662,    4486,    4171,    5209,    5972,    5652,    5285,
    5226,    6934,    6864,    6626,    7606,    7869,    7021,    6437,    9085,    7497,
    5957,    5745,    7134,    8882,    8375,    9861,    9350,    3653,    4769,    4094,
    5224,    5830,    5562,    4819,    5339,    5912,    6027,    6338,    6276,    3099,
    6843,    5881,    7578,    7169,    6319,    6528,    4373,    4470,    5694,    4112,
    5116,    4426,    3322,    4510,    2729,    3624,    6352,    8050,    7340,    7141,
    7728,    8947,    6488,    7276,    8432,    6107,    8012,    7603,    6766,    5345,
    4821,    7274,    7803,    1906,    1517,    1639,    2086,    2935,    3574,    2823,
    3677,    2983,    2469,    2130,    1024,    1254,    1829,    2340,    2837,    3156,
     666,    1614,    1377,    2135,    2720,    2208,    1586,    2762,    3565,    3457,
       0,    1071,    1582,    2037,    2494,     933,    1111,     834,     876,    1084,
    2447,    1575,    1834,    2702,    2377,    1478,    2175,    1805,    1860,    2368,
    2749,    2795,    3707,    2155,    2758,    3328,    2405,    3466,    2499,    2580,
    2564,    3119,    3129,    3616,    4170,    3165,    3159,    3123,    4257,    3763,
    3716,    4460,    4849,    4312,    4797,    4062,    5869,    6217,    5917,    3987,
    5177,    4235,    5646,    5139,    6936,    6449,    3958,    5431,    4880,    5605,
    6157,    4810,    4888,    6030,    6727,    5475,    7153,    6722,    4137,    7479,
    6058,    7858,    7449,    6523,    6375,    4653,    4547,    5444,    4241,    4845,
    4234,    3240,    4323,    2654,    3252,    6529,    7897,    7187,    6988,    7575,
    8794,    6335,    6966,    8279,    5954,    7859,    7450,    6613,    4973,    4474,
    7121,    7650,    2390,    1869,    1465,    2324,    2563,    2678,    2452,    3251,
    2455,    1941,    1571,    1907,    1242,    1301,    1633,    2020,    2365,     968,
     934,     927,    1470,    1978,    1137,     515,    1691,    2494,    2929,    1071,
       0,     511,     966,    1423,     931,     583,     236,     460,    1610,    1376,
     811,     763,    1568,    1306,    1216,    1104,    1733,    2355,    1524,    1678,
    1703,    2636,    1779,    1925,    2257,    1829,    2395,    2286,    2857,    2095,
    2599,    2298,    2764,    2971,    2759,    3233,    2913,    3653,    3092,    4105,
    4335,    4281,    4701,    5186,    4282,    5198,    6346,    5163,    3453,    4506,
    4395,    6035,    5528,    7352,    6668,    2887,    4360,    3809,    4534,    5106,
    4139,    3817,    4959,    5645,    4804,    6071,    5683,    3066,    6440,    4994,
    8286,    7877,    6471,    6323,    5081,    4715,    5419,    4189,    4820,    4209,
    3393,    4298,    2806,    3227,    6302,    7845,    7135,    6936,    7523,    8742,
    6283,    6931,    8227,    5902,    7807,    7398,    6561,    4938,    4439,    7069,
    7598,    2818,    2297,    1893,    2462,    2739,    2351,    2353,    3068,    2263,
    1842,    1447,    2439,    1804,    1230,    1412,    1694,    2091,    1479,     762,
    1278,    1143,    1651,     810,     343,    1378,    2167,    2762,    1582,     511,
       0,     454,     911,    1254,     895,     747,     933,    1763,     864,     928,
     546,    1056,     789,    1378,    1062,    1815,    2437,    1255,    1171,    1181,
    2092,    1737,    1674,    1750,    1787,    1888,    2244,    2815,    2081,    2557,
    2029,    2171,    2454,    2564,    3191,    2871,    3060,    2902,    4063,    4231,
    3993,    4659,    5144,    4240,    4708,    6304,    4973,    3324,    4016,    4353,
    5993,    5486,    7228,    6626,    2357,    3853,    3279,    4027,    4599,    3671,
    3310,    4452,    5123,    4336,    5549,    5176,    2554,    5933,    4477,    8623,
    8219,    6664,    6288,    5403,    4616,    5298,    4160,    4699,    4088,    3711,
    4177,    3017,    3106,    6181,    7798,    7088,    6889,    7476,    8695,    6236,
    6810,    8180,    5837,    7760,    7351,    6514,    4817,    4318,    7022,    7551,
    3354,    2833,    2429,    2689,    2900,    2096,    2295,    3010,    2187,    1900,
    1885,    2878,    2213,    1713,    1451,    1618,    2015,    1934,    1200,    1741,
    1182,    1484,     849,     781,    1109,    2004,    2691,    2037,     966,     454,
       0,     457,    1623,    1360,    1202,    1380,    2103,     656,    1234,     852,
     596,    1012,    1684,    1368,    2121,    2743,    1479,    1310,     986,    1884,
    2043,    1869,    1889,    2093,    2027,    2550,    3121,    2406,    2799,    2138,
    2329,    2618,    2740,    3497,    3177,    3218,    2905,    4369,    4395,    4157,
    4965,    5400,    4546,    4866,    6610,    4934,    3488,    4174,    4659,    6299,
    5792,    7392,    6881,    2149,    3869,    3071,    4169,    4741,    3829,    3452,
    4439,    5022,    4494,    5448,    5318,    2100,    5943,    4632,    8073,    7663,
    6202,    5989,    5556,    4154,    4836,    3698,    4237,    3626,    3340,    3715,
    2883,    2644,    5719,    7421,    6701,    6488,    7017,    8396,    5827,    6348,
    7717,    5375,    7461,    7052,    6215,    4355,    3856,    6682,    7110,    3295,
    2774,    2386,    2716,    2766,    1726,    1795,    2589,    1725,    1576,    1787,
    2889,    2318,    1699,    1317,    1156,    1553,    2155,    1273,    1745,     757,
    1022,     583,    1115,     680,    1542,    2229,    2487,    1423,     911,     457,
       0,    2080,    1818,    1659,    1446,    2562,     758,    1691,    1309,     478,
    1368,    2141,    1825,    2578,    3200,    1835,    1576,    1252,    1711,    2500,
    2225,    2203,    2550,    2341,    3007,    3578,    2863,    3107,    2446,    2685,
    2771,    3048,    3954,    3634,    3574,    3261,    4773,    4703,    4465,    5422,
    5708,    5003,    5222,    6981,    5290,    3796,    4530,    5116,    6721,    6214,
    7700,    7189,    1976,    3658,    2903,    4187,    4759,    4185,    3470,    4361,
    4944,    4628,    5370,    5298,    1941,    5865,    4650,    8413,    8004,    6895,
    6828,    5208,    5046,    5994,    4613,    5416,    4726,    3898,    4810,    3319,
    3917,    6901,    8350,    7640,    7441,    8028,    9247,    6788,    7576,    8732,
    6407,    8312,    7903,    7066,    5638,    5121,    7574,    8103,    2417,    1860,
    1932,    2395,    3228,    3498,    3108,    3823,    3223,    2721,    2341,    1838,
    1451,    2046,    2465,    2822,    3197,     904,    1759,    1671,    2290,    2798,
    1957,    1335,    2511,    3314,    3697,     933,     881,    1254,    1623,    2080,
       0,     408,     694,    1096,     716,    1923,     757,    1094,    2110,    1716,
     782,    1158,    1057,    1457,    1589,    1940,    2134,    2898,    1407,    1979,
    2519,    1653,    2657,    2154,    2205,    1723,    2362,    2363,    2818,    3282,
    2491,    2844,    2771,    3707,    3139,    3401,    4012,    3908,    3997,    4370,
    3684,    5224,    5701,    5217,    3239,    4532,    3920,    5331,    4824,    6420,
    5933,    3297,    4622,    4146,    4796,    5368,    4193,    4079,    5221,    5918,
    4858,    6344,    5945,    3784,    6702,    5305,    8243,    7834,    6846,    6779,
    5038,    5077,    5917,    4564,    5318,    4677,    3713,    4761,    3127,    3725,
    6852,    8301,    7591,    7392,    7979,    9198,    6739,    7439,    8683,    6358,
    8263,    7854,    7017,    5446,    4947,    7525,    8054,    2477,    1920,    1850,
    2346,    3036,    3139,    2901,    3616,    2928,    2414,    2044,    1929,    1264,
    1774,    2106,    2494,    2838,     995,    1432,    1312,    1931,    2439,    1598,
     976,    2152,    2955,    3402,    1111,     555,     895,    1353,    1818,     441,
       0,     393,     817,    1105,    1629,     441,     800,    1784,    1398,     736,
     904,    1234,    1775,    1320,    1686,    1726,    2644,    1524,    1725,    2265,
    1614,    2403,    2031,    2423,    1880,    2344,    2094,    2564,    2930,    2559,
    2978,    2658,    3453,    2892,    3691,    4080,    4060,    4287,    4757,    4037,
    4998,    6088,    4963,    3198,    4306,    4210,    5621,    5114,    6807,    6320,
    3003,    4368,    3794,    4542,    5114,    3939,    3825,    4967,    5664,    4604,
    6090,    5691,    3316,    6448,    4953,    7896,    7487,    6587,    6520,    4691,
    4730,    5570,    4305,    4971,    4360,    3366,    4449,    2780,    3378,    6593,
    8042,    7332,    7133,    7720,    8939,    6480,    7092,    8424,    6099,    8004,
    7595,    6758,    5099,    4600,    7266,    7795,    2218,    1661,    1503,    2087,
    2689,    2914,    2578,    3396,    2581,    2067,    1697,    1670,    1005,    1427,
    1759,    2147,    2491,     731,    1139,     965,    1706,    2214,    1373,     751,
    1927,    2730,    3055,     834,     236,     747,    1202,    1659,     694,     393,
       0,     498,    1411,    1612,     769,     999,    1804,    1542,    1135,    1340,
    1752,    2152,    1713,    1914,    1939,    2872,    1957,    2161,    2493,    2007,
    2631,    2522,    2900,    2273,    2835,    2487,    3000,    3207,    2995,    3469,
    3149,    3889,    3328,    4119,    4571,    4459,    4785,    5065,    4379,    5434,
    6396,    5399,    3689,    4742,    4702,    6078,    5571,    7115,    6628,    3123,
    4596,    4045,    4770,    5342,    4375,    4053,    5195,    5881,    5040,    6307,
    5919,    3302,    6676,    5230,    7438,    7029,    6179,    6135,    4233,    4272,
    5183,    4001,    4584,    3973,    3124,    4062,    2393,    2991,    6212,    7657,
    6947,    6748,    7335,    8554,    6095,    6705,    8039,    5714,    7619,    7210,
    6373,    4712,    4213,    6881,    7410,    1970,    1449,    1045,    1910,    2302,
    2484,    2190,    2969,    2168,    1654,    1284,    1444,     873,    1014,    1346,
    1734,    2078,     604,     712,     538,    1284,    1869,     943,     590,    1497,
    2300,    2642,     876,     460,     919,    1377,    1427,    1096,     845,     498,
       0,    1813,    1797,     993,    1223,    1888,    1766,    1398,    1564,    1855,
    2554,    1995,    2138,    2101,    3096,    2239,    2385,    2717,    2289,    2855,
    2746,    3044,    2585,    3059,    2769,    3224,    3374,    3219,    3693,    3373,
    4113,    3552,    4521,    4795,    4771,    5204,    5467,    4781,    5658,    6798,
    5623,    3913,    4966,    4855,    6480,    5973,    7517,    7030,    3290,    4801,
    4126,    4990,    5566,    4599,    4277,    5371,    5944,    5264,    6370,    6143,
    2982,    6875,    5397,    8662,    8253,    7403,    8553,    5457,    5554,    6900,
    5196,    6301,    5690,    4406,    5779,    3813,    4708,    7436,    9495,    8775,
    8562,    9091,   10972,    7901,    8422,    9791,    7449,   10037,    9628,    8346,
    6429,    5930,    8756,    9184,    2990,    2601,    2723,    3170,    4019,    4453,
    3907,    4761,    4067,    3553,    3214,    2108,    2338,    2913,    3424,    3482,
    4240,    1736,    2432,    2339,    2931,    3439,    2598,    1976,    3448,    4269,
    4541,    1084,    1610,    1912,    2218,    2675,     737,    1109,    1443,    1872,
       0,    2211,     956,    1382,    2491,    2004,     589,    1062,     735,     741,
    1479,    1830,    2422,    2788,    1085,    1987,    2409,    1335,    2547,    1438,
    1489,    1494,    1905,    2059,    2546,    3100,    2095,    2141,    2055,    3187,
    2693,    2706,    3296,    3727,    3302,    3654,    2968,    4799,    4985,    4638,
    2914,    4107,    3225,    4636,    4129,    5704,    5217,    3585,    4512,    3854,
    4686,    5087,    3740,    4173,    5111,    5808,    4405,    6422,    5652,    4072,
    6409,    4988,    9142,    8738,    6948,    6572,    5922,    4900,    5582,    4444,
    4983,    4372,    4086,    4461,    3643,    3390,    6465,    8001,    7281,    7068,
    7597,    8111,    6407,    6703,    7596,    5955,    7188,    6767,    6798,    4935,
    4853,    6450,    6967,    3681,    3160,    2756,    3325,    3602,    2143,    2541,
    3294,    2471,    2322,    2295,    3304,    2669,    2093,    2063,    1902,    2431,
    2344,    1610,    2141,    1503,    1645,    1342,    1191,    1236,    2057,    2982,
    2447,    1376,     864,     656,     758,    1923,    1629,    1612,    1799,    2211,
       0,    1281,     911,     279,     561,    1473,    1156,    1940,    2531,    1028,
     817,     493,    1391,    1802,    1418,    1396,    1852,    1534,    2338,    2909,
    2118,    2348,    1687,    1878,    2012,    2289,    3285,    2965,    2767,    2454,
    4014,    3944,    3706,    4686,    4949,    4263,    4415,    6222,    4483,    3037,
    3723,    4447,    5962,    5455,    6941,    6430,    1656,    3282,    2578,    3676,
    4248,    3378,    2959,    3852,    4435,    4043,    4861,    4789,    1860,    5356,
    4129,    8391,    7982,    7132,    7015,    5186,    5168,    6065,    4881,    5466,
    4855,    3861,    4944,    3275,    3873,    6948,    8537,    7827,    7628,    8215,
    9434,    6975,    7587,    8919,    6594,    8499,    8090,    7253,    5594,    5095,
    7761,    8290,    2923,    2402,    1998,    2857,    3184,    3420,    3073,    3891,
    3076,    2562,    2192,    2432,    1775,    1922,    2254,    2632,    2986,    1472,
    1582,    1460,    2081,    2589,    1748,    1126,    2376,    3399,    3550,    1575,
     731,     928,    1234,    1691,     757,     441,     769,     993,     956,    1341,
       0,     512,    1621,    1134,     404,     516,     861,    1483,     947,    1298,
    1552,    2256,    1136,    1337,    1877,    1279,    2015,    1643,    2050,    1545,
    1956,    1721,    2176,    2730,    2171,    2590,    2270,    3065,    2504,    3399,
    3692,    3672,    3995,    4480,    3745,    4610,    6224,    4575,    2810,    3918,
    3752,    5329,    4822,    6802,    6456,    2715,    3980,    3637,    4154,    4726,
    3551,    3437,    4579,    5276,    4216,    5702,    5303,    3202,    6060,    4799,
    8621,    8212,    6901,    6753,    5416,    5120,    6000,    4619,    5418,    4651,
    3813,    4735,    3227,    3825,    6900,    8275,    7565,    7366,    7953,    9172,
    6713,    7501,    8657,    6332,    8237,    7828,    6991,    5546,    5046,    7499,
    8028,    3153,    2632,    2228,    2859,    3136,    2848,    2783,    3498,    2718,
    2272,    1997,    2691,    2056,    1825,    2206,    2180,    2638,    1731,    1312,
    1651,    1690,    2222,    1357,     893,    1861,    2742,    3192,    1834,     763,
     546,     852,    1309,    1094,     800,     999,    1223,    1382,     902,     512,
       0,    1182,     733,     848,     532,    1285,    1907,     963,    1105,    1130,
    2063,    1207,    1370,    1684,    1257,    1822,    1714,    2285,    1523,    2027,
    1737,    2209,    2398,    2187,    2661,    2341,    3098,    2520,    3533,    3763,
    3709,    4129,    4614,    3710,    4626,    5774,    4591,    2881,    3934,    3823,
    5463,    4956,    6936,    6096,    2314,    3787,    3236,    3961,    4533,    3567,
    3244,    4386,    5072,    4232,    5498,    5110,    2801,    5867,    4421,    8539,
    8129,    6668,    6292,    5859,    4620,    5302,    4164,    4703,    4092,    3806,
    4181,    3349,    3110,    6185,    7721,    7001,    6788,    7317,    7831,    6127,
    6423,    7316,    5675,    6908,    6487,    6518,    4655,    4573,    6170,    6687,
    3761,    3240,    2973,    3182,    3232,    1863,    2261,    3014,    2191,    2042,
    2253,    3504,    2839,    2165,    1783,    1622,    2151,    2570,    1733,    2222,
    1223,    1365,    1049,    1407,     956,    1777,    2702,    2702,    1597,    1119,
     596,     478,    2203,    1909,    1833,    1913,    2491,     279,    1561,    1191,
       0,     841,    1753,    1436,    2220,    2811,    1308,    1097,     773,    1251,
    2082,    1698,    1676,    2132,    1814,    2618,    3189,    2398,    2628,    1967,
    2158,    2292,    2569,    3565,    3245,    3047,    2734,    4294,    4224,    3986,
    4966,    5229,    4543,    4695,    6502,    4763,    3317,    4003,    4727,    6242,
    5735,    7221,    6710,    1516,    3198,    2443,    3727,    4299,    3658,    3010,
    3901,    4484,    4168,    4910,    4838,    1580,    5405,    4190,    8950,    8546,
    7116,    6968,    5730,    5360,    6209,    4834,    5610,    4866,    4038,    4950,
    3451,    4017,    7092,    8490,    7780,    7581,    8159,    8643,    6928,    7490,
    8128,    6517,    7720,    7299,    7206,    5497,    5261,    6982,    7499,    3696,
    3175,    2771,    3225,    3675,    2675,    2998,    3713,    2933,    2487,    2212,
    3215,    2550,    2040,    2364,    2395,    2993,    2274,    1527,    2068,    1919,
    2207,    1762,    1108,    1798,    2619,    3407,    2377,    1306,     789,    1012,
    1368,    1716,    1422,    1542,    1707,    2004,     561,    1089,     719,     841,
       0,    1266,     776,    1733,    2327,     532,     388,     403,    1346,    1601,
     875,     967,    1466,    1105,    2108,    2679,    1762,    1967,    1306,    1407,
    1784,    1902,    2869,    2519,    2296,    1983,    3633,    3563,    3283,    4305,
    4568,    3882,    3944,    5841,    4012,    2609,    3252,    4031,    5581,    5074,
    6560,    6049,    1566,    3070,    2488,    3244,    3816,    2907,    2527,    3669,
    4366,    3572,    4792,    4393,    2018,    5150,    3707,    8796,    8387,    7537,
    7588,    5591,    5573,    6470,    5332,    5871,    5260,    4266,    5349,    3680,
    4278,    7353,    9065,    8345,    8132,    8661,   10007,    7471,    7992,    9361,
    7019,    9072,    8663,    7826,    5999,    5500,    8326,    8754,    3177,    2698,
    2403,    3155,    3589,    3715,    3478,    4331,    3481,    2967,    2597,    2502,
    2118,    2327,    2659,    3037,    3391,    1664,    1987,    1865,    2486,    3119,
    2153,    1531,    2710,    3531,    3955,    1478,    1216,    1378,    1684,    2141,
     782,     736,    1135,    1398,     589,    1473,     404,     848,    1753,    1174,
       0,     473,     565,    1154,     890,    1241,    1502,    2199,     901,    1280,
    1820,    1044,    1958,    1408,    1754,    1254,    1721,    1664,    2119,    2500,
    1911,    2355,    2035,    3012,    2518,    3103,    3457,    3437,    3699,    4067,
    3381,    4624,    5398,    4454,    2575,    3932,    3517,    5033,    4526,    6117,
    5630,    2847,    3923,    3265,    4097,    4669,    3565,    3380,    4522,    5219,
    4230,    5645,    5246,    3334,    6003,    4523,    8962,    8553,    7282,    7269,
    5757,    5461,    6358,    5135,    5759,    5148,    4154,    5237,    3568,    4166,
    7241,    8791,    8081,    7882,    8469,    9688,    7229,    7880,    9173,    6848,
    8753,    8344,    7507,    5887,    5388,    8015,    8544,    3366,    2809,    2569,
    3200,    3477,    3254,    3299,    4014,    3234,    2788,    2485,    2818,    2153,
    2215,    2547,    2696,    3544,    1884,    1828,    1992,    2206,    2802,    1873,
    1409,    2377,    3214,    3708,    2150,    1104,    1062,    1368,    1825,    1158,
     889,    1286,    1510,    1062,    1140,     516,     532,    1420,     735,     473,
       0,     960,    1435,     465,     816,    1063,    1774,     709,     855,    1395,
     759,    1533,    1216,    1787,    1025,    1529,    1239,    1694,    2075,    1689,
    2163,    1843,    2583,    2022,    3035,    3265,    3211,    3631,    4116,    3212,
    4128,    5276,    4093,    2383,    3436,    3325,    4965,    4458,    6438,    5598,
    2427,    3498,    2840,    3672,    4244,    3069,    2955,    4097,    4794,    3734,
    5220,    4821,    2879,    5578,    4098,    9383,    8974,    7953,    7886,    6178,
    6090,    6987,    5671,    6388,    5777,    4783,    5866,    4197,    4795,    7959,
    9408,    8698,    8499,    9086,   10305,    7846,    8509,    9790,    7465,    9370,
    8961,    8124,    6516,    6017,    8632,    9161,    3475,    2996,    2860,    3453,
    4106,    4182,    3995,    4848,    3998,    3484,    3114,    2826,    2529,    2844,
    3176,    3554,    3908,    1962,    2504,    2322,    3003,    3586,    2670,    2048,
    3177,    3998,    4472,    1805,    1733,    1815,    2121,    2578,    1057,    1234,
    1752,    1855,     735,    1940,     861,    1285,    2220,    1637,     565,     960,
       0,     622,    1353,    1728,    1965,    2686,     414,    1179,    1761,     660,
    1923,     890,    1188,     730,    1234,    1362,    1875,    2384,    1424,    1870,
    1565,    2516,    2022,    2549,    2987,    2915,    3145,    3565,    2879,    4128,
    4896,    3967,    2088,    3436,    2757,    4479,    3972,    5615,    5128,    3148,
    3872,    3248,    4000,    4416,    3069,    3345,    4380,    5168,    3734,    5594,
    4981,    3791,    5738,    4317,    9438,    9029,    8179,    8450,    6233,    6330,
    7616,    5972,    7038,    6348,    5182,    6432,    4589,    5484,    8212,    9972,
    9262,    9063,    9650,   10869,    8410,    9198,   10354,    8029,    9934,    9525,
    8688,    7205,    6706,    9196,    9725,    3766,    3377,    3499,    3946,    4795,
    4773,    4683,    5475,    4620,    4106,    3736,    2884,    3114,    3466,    3798,
    4176,    4530,    2512,    3126,    3046,    3625,    4177,    3292,    2670,    3768,
    4589,    5094,    1860,    2355,    2437,    2743,    3200,    1513,    1775,    2191,
    2579,     790,    2531,    1483,    1907,    2811,    2308,    1187,    1435,     622,
       0,    1852,    2203,    2636,    3161,     802,    1672,    2303,    1068,    2416,
     667,     748,    1166,    1287,    1731,    2218,    2772,    1660,    1337,    1291,
    2789,    2143,    1967,    2555,    2986,    2650,    2913,    2227,    4401,    4244,
    4085,    2155,    3709,    2550,    3926,    3419,    4963,    4476,    3690,    4381,
    3723,    4520,    4689,    3342,    3842,    4653,    5710,    4007,    6028,    5254,
    4266,    6011,    4590,    9393,    8984,    7713,    7687,    6188,    5892,    6789,
    5553,    6190,    5579,    4585,    5668,    3999,    4597,    7672,    9030,    8310,
    8097,    8626,    9383,    7436,    7957,    8868,    6984,    8460,    8039,    7881,
    5964,    5819,    7722,    8239,    3925,    3404,    3000,    3631,    3908,    3270,
    3717,    4432,    3565,    3206,    2916,    3463,    2828,    2646,    2697,    2996,
    3460,    2503,    2092,    2423,    2428,    2674,    2095,    1636,    2265,    3086,
    4042,    2368,    1535,    1284,    1479,    1835,    1589,    1335,    1771,    1995,
    1479,    1028,     947,     980,    1308,     532,     890,     465,    1377,    1852,
       0,     408,     856,    1366,    1060,     397,     987,     932,    1125,    1633,
    2204,    1223,    1442,     781,    1236,    1617,    1377,    2344,    1994,    2125,
    1715,    3212,    3142,    2904,    3812,    4147,    3393,    3773,    5420,    3786,
    2235,    3081,    3506,    5146,    4639,    6139,    5628,    2019,    3090,    2432,
    3233,    3836,    2736,    2547,    3675,    4386,    3401,    4812,    4413,    2471,
    5170,    3640,    9336,    8932,    7502,    7354,    6116,    5746,    6465,    5220,
    5866,    5252,    4424,    5336,    3837,    4273,    7348,    8819,    8099,    7886,
    8415,    8941,    7225,    7533,    8426,    6773,    8018,    7597,    7592,    5753,
    5647,    7280,    7797,    4068,    3547,    3143,    3611,    4047,    2973,    3384,
    4099,    3319,    2873,    2598,    3605,    2940,    2426,    2709,    2781,    3249,
    2646,    1913,    2454,    2305,    2463,    2107,    1494,    2054,    2875,    3793,
    2749,    1678,    1171,    1310,    1624,    1940,    1664,    1914,    2138,    1830,
     817,    1291,    1105,    1097,     385,    1234,     756,    1728,    2203,     405,
       0,     516,     958,    1470,     705,     579,    1296,     717,    1984,    2555,
    1574,    1634,     973,    1194,    1396,    1575,    2680,    2276,    2083,    1770,
    3300,    3230,    2992,    3972,    4235,    3549,    3731,    5508,    3799,    2323,
    3039,    3790,    5248,    4741,    6227,    5716,    1679,    2682,    2024,    2856,
    3428,    2694,    2139,    3281,    3978,    3359,    4404,    4005,    2131,    4762,
    3319,    9359,    8955,    7507,    7066,    6139,    5459,    6141,    5003,    5542,
    4931,    4447,    5020,    3860,    3949,    7024,    8495,    7775,    7562,    8091,
    8661,    6901,    7253,    8146,    6449,    7738,    7317,    7292,    5429,    5347,
    7000,    7517,    4011,    3490,    3086,    3634,    3932,    2455,    3073,    3788,
    3002,    2829,    2621,    3634,    2969,    2423,    2385,    2461,    2869,    2692,
    1936,    2471,    2062,    2139,    1783,    1517,    1730,    2551,    3476,    2795,
    1724,    1194,     986,    1300,    2033,    1734,    1960,    2129,    2422,     493,
    1361,    1138,     773,     403,    1598,    1165,    2176,    2651,     856,     516,
       0,     897,    1879,    1153,    1095,    1744,    1233,    2432,    3003,    2034,
    2094,    1433,    1624,    1731,    2035,    3128,    2736,    2513,    2200,    3760,
    3690,    3452,    4432,    4695,    4009,    4161,    5968,    4229,    2783,    3469,
    4250,    5708,    5201,    6687,    6176,    1162,    2788,    2084,    3228,    3849,
    3124,    2573,    3358,    3941,    3789,    4367,    4295,    1614,    4862,    3635,
   10188,    9784,    7901,    6846,    6968,    5853,    5981,    5397,    5403,    4744,
    5039,    4828,    4582,    4055,    6914,    8339,    7619,    7406,    7935,    8712,
    6745,    7266,    8197,    6293,    7789,    7368,    7072,    5273,    5127,    7051,
    7568,    5005,    4448,    4101,    4463,    4465,    2505,    3494,    3640,    3256,
    3275,    3450,    4457,    3792,    3278,    3016,    2855,    2769,    3523,    2765,
    3306,    2456,    2205,    2282,    2346,    1963,    2395,    3256,    3707,    2550,
    2092,    1884,    1711,    2815,    2516,    2786,    3010,    2788,    1391,    2143,
    1961,    1251,    1237,    2086,    1608,    2665,    3116,    1257,     852,     897,
       0,    2094,    1344,     864,    1921,     781,    2601,    3172,    2071,    2241,
    1580,    1362,    1171,    1941,    3143,    2793,    2285,    2132,    3828,    3713,
    3418,    4500,    4763,    4077,    3437,    6036,    4376,    2758,    2745,    4253,
    5776,    5269,    6755,    6244,    1141,    2577,    1919,    2751,    3323,    2767,
    2034,    3176,    3873,    2940,    4299,    3900,    1595,    4657,    3194,    9637,
    9228,    7957,    7944,    6432,    6136,    7033,    5810,    6434,    5823,    4829,
    5912,    4243,    4841,    7916,    9466,    8756,    8557,    9144,   10363,    7904,
    8555,    9848,    7523,    9428,    9019,    8182,    6562,    6063,    8690,    9219,
    3825,    3346,    3244,    3803,    4152,    3929,    3974,    4689,    3909,    3463,
    3160,    3176,    2828,    2890,    3222,    3371,    4219,    2312,    2503,    2667,
    2881,    3477,    2548,    2084,    3052,    3889,    4383,    2155,    1779,    1737,
    2043,    2500,    1407,    1524,    1961,    2185,    1085,    1815,    1136,    1207,
    2095,    1410,     885,     709,     414,     802,    1126,    1477,    1738,    2094,
       0,     823,    1405,     304,    1567,     565,    1136,     315,     878,     947,
    1435,    1989,     936,    1512,    1192,    2008,    1514,    2384,    2614,    2500,
    2980,    3465,    2561,    3620,    4625,    3585,    1732,    2928,    2674,    4314,
    3807,    5735,    4947,    2792,    3516,    2892,    3644,    3908,    2561,    2989,
    3872,    4812,    3226,    5238,    4473,    3540,    5230,    3809,    9717,    9313,
    7883,    7735,    6497,    6127,    6982,    5601,    6404,    5633,    4805,    5717,
    4218,    4987,    7889,    9257,    8547,    8348,    8935,    9431,    7695,    8347,
    8916,    7314,    8508,    8087,    7973,    6354,    6028,    7770,    8287,    4203,
    3646,    3390,    3992,    4298,    3463,    3765,    4480,    3700,    3254,    2979,
    3655,    2990,    2807,    3087,    3162,    3850,    2721,    2294,    2813,    2686,
    3064,    2485,    1875,    2655,    3476,    4174,    2758,    1909,    1674,    1854,
    2225,    1979,    1725,    2145,    2369,    1987,    1349,    1337,    1320,    1629,
     844,    1280,     818,    1268,    1672,     397,     705,    1153,    1344,     908,
       0,     652,     604,     814,    1415,    1986,     904,    1074,     413,     868,
    1422,    1009,    1976,    1626,    1757,    1347,    2848,    2928,    2647,    3444,
    3929,    3025,    3405,    5089,    3418,    1973,    2713,    3138,    4778,    4271,
    6251,    5411,    2316,    2779,    2121,    2953,    3715,    2368,    2236,    3378,
    4075,    3033,    4501,    4280,    2768,    5037,    3616,   10115,    9706,    8431,
    8803,    6910,    6362,    7044,    5906,    6445,    5834,    5303,    5923,    4717,
    4852,    7927,    9398,    8678,    8465,    8994,   10233,    7804,    8325,    9718,
    7352,    9310,    8889,    8249,    6332,    6372,    8572,    9089,    4647,    4126,
    3722,    4349,    4626,    3638,    4003,    4797,    3933,    3784,    3180,    4185,
    3550,    3364,    3288,    3364,    3828,    3225,    2495,    3141,    2965,    3042,
    2686,    2076,    2633,    3454,    4410,    3328,    2257,    1750,    1889,    2203,
    2519,    2265,    2493,    2717,    2409,    1396,    1877,    1684,    1676,     967,
    1820,    1395,    1926,    2347,     987,     579,    1095,     864,    1511,     652,
       0,    1380,     270,    1797,    2331,    1207,    1376,     715,     498,     949,
    1077,    2279,    1929,    1400,    1268,    2958,    2849,    2548,    3630,    3893,
    3207,    3048,    5166,    3150,    1894,    2356,    3389,    4906,    4399,    5885,
    5374,    1488,    2235,    1577,    2409,    2981,    2011,    1692,    2834,    3531,
    2553,    3957,    3558,    2263,    4315,    2872,    9687,    9278,    8007,    8094,
    6482,    6186,    7083,    5945,    6484,    5873,    4879,    5962,    4293,    4891,
    7966,    9616,    8906,    8707,    9274,   10513,    8054,    8605,    9974,    7632,
    9578,    9169,    8332,    6612,    6113,    8840,    9367,    4191,    3634,    3294,
    3925,    4202,    4065,    4091,    4839,    4059,    3580,    3210,    3429,    2978,
    2940,    3272,    3482,    4313,    2709,    2600,    2717,    2931,    3527,    2598,
    2144,    3118,    3939,    4533,    2405,    1829,    1787,    2093,    2550,    1845,
    1667,    2065,    2289,    1335,    1881,    1279,    1257,    2161,    1446,    1044,
     759,     664,    1068,     932,    1296,    1744,    1921,     304,     604,    1186,
       0,    1348,     811,    1382,     449,    1074,     817,    1304,    1809,    1073,
    1758,    1438,    1982,    1488,    2630,    2860,    2638,    3226,    3711,    2807,
    3594,    4871,    3559,    1964,    2902,    2920,    4560,    4053,    6033,    5193,
    2573,    3297,    2655,    3425,    3882,    2535,    2770,    3846,    4593,    3200,
    5019,    4447,    3359,    5204,    3783,   10053,    9649,    8219,    8071,    6833,
    6463,    7182,    5937,    6583,    5969,    5141,    6053,    4554,    4990,    8065,
    9536,    8816,    8603,    9132,    9345,    7942,    7937,    8830,    7490,    8422,
    8001,    8309,    6470,    6364,    7684,    8201,    4785,    4264,    3860,    4328,
    4764,    3025,    4101,    4816,    4036,    3590,    3315,    4322,    3657,    3143,
    3426,    3498,    3439,    3363,    2630,    3171,    3022,    2725,    2824,    2211,
    2771,    3592,    4510,    3466,    2395,    1888,    2027,    2341,    2657,    2381,
    2631,    2855,    2547,    1534,    2008,    1822,    1814,    1102,    1951,    1473,
    2012,    2416,    1122,     717,    1233,     871,    1723,     814,     270,    1348,
       0,    2067,    2601,    1477,    1646,     985,     762,     460,    1341,    2549,
    2199,    1254,    1532,    3228,    3113,    2818,    3900,    4163,    3477,    2726,
    5436,    3476,    2158,    2034,    3653,    5176,    4669,    6155,    5644,    1217,
    1948,    1306,    2076,    2710,    2154,    1421,    2518,    3244,    2229,    3670,
    3287,    2502,    4015,    2483,   10077,    9668,    8818,    8751,    6872,    6643,
    7540,    6402,    6941,    6330,    5336,    6419,    4750,    5348,    8824,   10135,
    9415,    9202,    9731,   11170,    8541,    9062,   10431,    8089,   10235,    9826,
    8986,    7069,    6570,    9396,    9824,    4223,    3744,    3751,    4318,    4659,
    4580,    4548,    5401,    4551,    4037,    3667,    3523,    3394,    3397,    3729,
    3939,    4770,    2827,    3057,    3174,    3388,    3984,    3055,    2601,    3575,
    4396,    5025,    2499,    2286,    2244,    2550,    3007,    1922,    2031,    2522,
    2746,    1457,    2338,    1643,    1714,    2618,    2108,    1408,    1216,     890,
     667,    1633,    1984,    2432,    2601,     565,    1415,    1798,     811,    2068,
       0,     603,     626,     619,    1120,    1607,    2199,    1011,    1007,     702,
    2178,    1481,    1805,    2124,    2428,    2475,    2751,    2056,    3763,    4082,
    3499,    1566,    3071,    2169,    3764,    3257,    4801,    4314,    3595,    4033,
    3375,    3909,    4078,    2731,    3231,    4042,    5455,    3396,    5417,    4643,
    4047,    5400,    3979,   10158,    9749,    8899,    9319,    6953,    7050,    8111,
    6692,    7512,    6901,    5902,    6990,    5309,    5919,    8932,   10706,    9986,
    9773,   10302,   11738,    9112,    9633,   11002,    8660,   10803,   10394,    9557,
    7640,    7141,    9967,   10395,    4486,    4097,    4219,    4666,    5230,    5151,
    5119,    5972,    5122,    4608,    4238,    3604,    3834,    3968,    4300,    4510,
    5341,    3232,    3628,    3511,    3959,    4555,    3626,    3172,    4146,    4967,
    5596,    2580,    2857,    2815,    3121,    3578,    2265,    2423,    3053,    3044,
    1562,    2909,    2050,    2285,    3189,    2679,    1754,    1787,    1188,     758,
    2204,    2555,    3003,    3172,    1136,    1986,    2331,    1382,    2601,     603,
       0,    1197,    1064,    1653,    2108,    2649,    1476,     579,     531,    2366,
    1801,    1219,    1807,    2308,    1868,    2165,    1465,    4012,    3496,    3389,
    1477,    3320,    1601,    3178,    2671,    4215,    3728,    4166,    4487,    3908,
    4359,    4266,    2919,    3681,    4230,    5643,    3584,    5605,    4831,    4618,
    5588,    4167,   10000,    9591,    8320,    8260,    6795,    6499,    7396,    6126,
    6797,    6158,    5192,    6242,    4606,    5204,    8279,    9782,    9072,    8873,
    9460,   10679,    8220,    8918,   10164,    7839,    9744,    9335,    8498,    6925,
    6426,    9006,    9535,    4141,    3662,    3607,    4119,    4515,    4245,    4290,
    5005,    4225,    3779,    3504,    3492,    3144,    3253,    3585,    3687,    4535,
    2628,    2819,    3030,    3211,    3840,    2911,    2400,    3368,    4252,    4699,
    2564,    2142,    2100,    2379,    2863,    1723,    1880,    2277,    2501,    1494,
    2131,    1507,    1523,    2411,    1713,    1201,    1072,     730,    1166,    1223,
    1598,    2024,    2071,     315,     871,    1207,     449,    1477,     626,    1197,
       0,     638,     591,    1078,    1632,     621,    1345,     995,    1719,    1225,
    2217,    2395,    2185,    2813,    3298,    2394,    3331,    4458,    3296,    1492,
    2639,    2507,    4147,    3640,    5420,    4780,    2695,    3416,    2784,    3431,
    3619,    2272,    2756,    3583,    4712,    2937,    4958,    4184,    3671,    4941,
    3520,   10457,   10048,    8777,    8899,    7252,    6956,    7853,    6715,    7254,
    6643,    5649,    6732,    5063,    5661,    8736,   10421,    9711,    9512,   10044,
   10648,    8854,    9375,   10133,    8402,    9725,    9304,    9137,    7382,    6883,
    8987,    9504,    4753,    4274,    4064,    4695,    4972,    4680,    4861,    5644,
    4864,    4350,    3980,    4104,    3756,    3710,    4042,    4326,    4895,    3240,
    3370,    3487,    3701,    4109,    3368,    2914,    3700,    4521,    5338,    3119,
    2599,    2557,    2914,    3270,    2335,    2344,    2835,    3059,    1905,    2463,
    1956,    2027,    2743,    1967,    1721,    1529,    1234,    1287,    1442,    1778,
    2226,    2241,     878,    1074,    1377,    1074,    1647,     619,    1064,     638,
       0,     670,    1033,    1574,     402,     991,     641,    1443,     885,    1863,
    1877,    1784,    2459,    2944,    2040,    3212,    4104,    2948,     922,    2520,
    2153,    3793,    3286,    5026,    4426,    2865,    3412,    2954,    3284,    3343,
    1996,    2606,    3307,    4720,    2661,    4682,    3908,    3841,    4665,    3244,
   10167,    9758,    8487,    8429,    6962,    6666,    7563,    6295,    6964,    6327,
    5359,    6411,    4773,    5371,    8446,    9804,    9084,    8871,    9400,   10125,
    8210,    8731,    9610,    7758,    9202,    8781,    8655,    6738,    6593,    8464,
    8981,    4699,    4178,    3774,    4405,    4682,    4044,    4459,    5174,    4339,
    3948,    3673,    4237,    3602,    3420,    3471,    3770,    4234,    3277,    2866,
    3197,    3202,    3448,    2869,    2410,    3039,    3860,    4816,    3129,    2309,
    2058,    2253,    2609,    2363,    2109,    2545,    2769,    2059,    1802,    1721,
    1754,    2082,    1306,    1664,    1239,    1388,    1731,     781,    1117,    1565,
    1580,     948,     413,     716,     817,     986,    1120,    1653,     591,     670,
       0,     525,    1079,     605,    1601,    1251,    1414,     943,    2440,    2370,
    2132,    3069,    3375,    2650,    3062,    4648,    3014,    1463,    2370,    2763,
    4388,    3881,    5367,    4856,    2204,    2951,    2293,    2930,    3372,    2025,
    2252,    3431,    4247,    2690,    4711,    3937,    3180,    4694,    3273,   10432,
   10028,    8598,    8450,    7212,    6842,    7697,    6316,    7119,    6348,    5520,
    6432,    4933,    5723,    8604,    9880,    9160,    8947,    9476,    9807,    8286,
    8399,    9292,    7834,    8884,    8463,    8688,    6814,    6743,    8146,    8663,
    5154,    4633,    4229,    4707,    5137,    3600,    4480,    5195,    4415,    3969,
    3694,    4692,    4036,    3522,    3681,    3846,    4014,    3732,    3009,    3550,
    3401,    3300,    3079,    2590,    3115,    3936,    4889,    3616,    2764,    2171,
    2329,    2685,    2818,    2564,    3000,    3224,    2546,    1878,    2176,    2205,
    2158,    1407,    2119,    1694,    1875,    2218,    1236,    1096,    1624,    1362,
    1435,     868,     498,    1304,     762,    1607,    2086,    1078,    1021,     525,
       0,     553,     681,    1911,    1620,     901,     801,    2532,    2445,    2122,
    3204,    3467,    2781,    2549,    4740,    2651,    1498,    1857,    2993,    4480,
    3973,    5459,    4948,    1987,    2352,    2087,    2249,    2859,    1512,    1571,
    2750,    3648,    2127,    4074,    3424,    3031,    4181,    2571,   10580,   10176,
    8746,    8598,    7360,    6990,    7707,    6464,    7108,    6496,    5668,    6580,
    5081,    5515,    8590,   10115,    9395,    9182,    9414,    9781,    8521,    8373,
    9266,    8069,    8858,    8437,    8836,    7049,    6891,    8120,    8637,    5397,
    4840,    4783,    4855,    5691,    3449,    4628,    5343,    4563,    4117,    3842,
    4849,    4184,    3670,    4105,    4025,    3863,    3915,    3157,    3698,    3549,
    3149,    3441,    2738,    3350,    4171,    4200,    4170,    2942,    2551,    2687,
    2883,    3207,    2908,    3178,    3402,    3100,    2103,    2535,    2353,    2383,
    1629,    2478,    2000,    2429,    2772,    1649,    1244,    1844,    1447,    1989,
    1422,     797,    1858,     526,    2195,    2640,    1632,    1574,    1079,     553,
       0,    1222,    2452,    2161,     793,    1141,    3086,    2777,    2454,    3758,
    4021,    3335,    2201,    5294,    2995,    2039,    1509,    3464,    5034,    4527,
    6013,    5502,    1617,    1954,    1706,    1914,    2521,    1175,    1236,    2415,
    3250,    1768,    3676,    3086,    2902,    3843,    2212,   10617,   10208,    8914,
    8766,    7412,    7116,    8013,    6632,    7414,    6664,    5809,    6748,    5223,
    5821,    8896,   10288,    9578,    9379,    9966,   10386,    8726,    9514,    9871,
    8345,    9463,    9042,    9004,    7542,    7043,    8725,    9242,    4762,    4283,
    4224,    4740,    5132,    4494,    4796,    5511,    4731,    4285,    4010,    4113,
    3765,    3838,    4202,    4193,    4830,    3249,    3325,    3647,    3708,    4044,
    3375,    2906,    3635,    4456,    5205,    3165,    2759,    2564,    2849,    3205,
    2344,    2501,    2898,    3122,    2095,    2380,    2128,    2144,    2660,    1875,
    1822,    1689,    1351,    1660,    1377,    1579,    2161,    1941,     936,    1009,
    1077,    1073,    1341,    1011,    1476,     621,     402,     605,     681,    1222,
       0,    1256,     961,    1113,     586,    1982,    1845,    1564,    2654,    2917,
    2192,    2725,    4171,    2685,     890,    2033,    2220,    3858,    3351,    4909,
    4398,    2566,    2887,    2666,    2902,    3013,    1666,    2227,    2977,    4183,
    2331,    4352,    3578,    3610,    4335,    2914,   10737,   10328,    9478,    9534,
    7532,    7590,    8487,    7319,    7888,    7277,    6283,    7366,    5697,    6295,
    9511,   11056,   10346,   10147,   10678,   11953,    9488,   10009,   11378,    9036,
   11018,   10609,    9772,    8016,    7517,   10280,   10771,    5002,    4523,    4698,
    5101,    5606,    5527,    5495,    6348,    5498,    4984,    4614,    4183,    4207,
    4344,    4676,    4886,    5717,    3640,    4004,    4121,    4335,    4931,    4002,
    3548,    4522,    5343,    5972,    3159,    3233,    3191,    3497,    3954,    2735,
    2978,    3430,    3693,    2141,    3285,    2590,    2661,    3565,    2869,    2327,
    2163,    1761,    1337,    2344,    2680,    3128,    3143,    1512,    1976,    2279,
    1758,    2549,    1007,     579,    1345,     991,    1601,    1911,    2452,    1256,
       0,     349,    2132,    1567,     886,    1401,    2074,    1482,    1967,    1063,
    3778,    3127,    3143,    1243,    3086,    1176,    2816,    2309,    4289,    3449,
    3767,    4290,    3856,    4162,    4032,    2685,    3484,    3996,    5409,    3350,
    5371,    4597,    4743,    5354,    3933,   10701,   10292,    9442,    9372,    7496,
    7270,    8167,    7029,    7568,    6957,    5963,    7046,    5377,    5975,    9475,
   10762,   10042,    9829,   10358,   11791,    9168,    9689,   11058,    8716,   10856,
   10447,    9610,    7696,    7197,   10023,   10451,    4961,    4482,    4378,    5009,
    5286,    5207,    5175,    6028,    5178,    4664,    4294,    4147,    4132,    4024,
    4356,    4566,    5397,    3565,    3684,    3801,    4015,    4611,    3682,    3228,
    4202,    5023,    5652,    3123,    2913,    2871,    3177,    3634,    2660,    2658,
    3149,    3373,    2081,    2965,    2270,    2341,    3245,    2519,    2035,    1843,
    1565,    1291,    1994,    2330,    2778,    2793,    1192,    1626,    1929,    1438,
    2199,     702,     531,     995,     641,    1251,    1620,    2161,     961,     349,
       0,    2002,    1343,    1221,    1433,    1837,    1817,    2302,    1398,    3541,
    3462,    2918,    1006,    2849,    1511,    3151,    2644,    4569,    3784,    3417,
    3944,    3506,    3871,    3902,    2555,    3193,    3866,    5240,    3220,    5241,
    4467,    4393,    5224,    3803,   11493,   11089,    9659,    9511,    8273,    7903,
    8758,    7377,    8180,    7409,    6581,    7493,    5994,    6715,    9665,   10769,
   10049,    9836,   10365,   10872,    9175,    9464,   10357,    8723,    9949,    9528,
    9620,    7703,    7804,    9211,    9728,    5813,    5334,    5118,    5749,    6026,
    4661,    5541,    6256,    5304,    5030,    4755,    5164,    4900,    4583,    4570,
    4735,    5075,    4300,    4070,    4541,    4336,    4361,    3968,    3651,    4004,
    4825,    5781,    4257,    3653,    3060,    3218,    3574,    3395,    3453,    3889,
    4113,    3187,    2767,    3065,    3098,    3047,    2296,    2873,    2583,    2402,
    2789,    2125,    2083,    2513,    2399,    1987,    1757,    1400,    1982,    1621,
    2115,    2366,    1672,    1443,    1414,     901,     958,    1113,    2132,    2002,
       0,     564,    2639,    2147,    1838,    3311,    3574,    2888,    1648,    4645,
    2404,    1447,     956,    2827,    4438,    4080,    5402,    4891,    2569,    2317,
    2520,    1929,    1936,     589,    1331,    1900,    3313,    1254,    3275,    2501,
    3854,    3258,    1837,   10950,   10541,    9228,    9080,    7745,    7449,    8327,
    6946,    7747,    6978,    6142,    7062,    5556,    6154,    9229,   10456,    9736,
    9523,   10052,   10502,    8862,    9094,    9987,    8410,    9579,    9158,    9307,
    7390,    7373,    8841,    9358,    5248,    4769,    4557,    5188,    5465,    4295,
    5110,    5825,    4991,    4599,    4324,    4599,    4335,    4152,    4535,    4422,
    4709,    3735,    3639,    3980,    4031,    3995,    3713,    3220,    3691,    4512,
    5468,    3763,    3092,    2902,    2905,    3261,    2830,    2892,    3328,    3552,
    2693,    2454,    2504,    2520,    2734,    1983,    2308,    2022,    1837,    2143,
    1715,    1770,    2200,    2132,    1422,    1347,    1268,    1488,    1457,    1481,
    1801,    1107,     885,     943,     801,    1145,     586,    1567,    1343,     564,
       0,    2228,    1865,    1490,    2804,    3163,    2426,    2176,    4363,    2105,
     917,    1484,    2412,    4092,    3585,    5106,    4595,    2682,    2665,    2782,
    2537,    2464,    1117,    1859,    2428,    3841,    1782,    3803,    3029,    3726,
    3786,    2365,   11294,   10885,   10035,   10162,    8089,    8186,    9328,    7828,
    8750,    8060,    7038,    8144,    6445,    7340,   10068,   11684,   10974,   10775,
   11362,   12581,   10122,   10910,   12066,    9741,   11646,   11237,   10400,    9061,
    8455,   10908,   11437,    5622,    5151,    5355,    5729,    6651,    6399,    6472,
    7187,    6449,    6003,    5705,    4740,    4835,    5410,    5548,    5758,    6589,
    4268,    4876,    5114,    5207,    5803,    4874,    4420,    5394,    6215,    6923,
    3716,    4105,    4063,    4369,    4826,    3363,    3691,    4058,    4460,    2706,
    4157,    3399,    3533,    4437,    3741,    3005,    3035,    2439,    2110,    3216,
    3552,    4000,    4015,    2384,    2848,    3151,    2630,    3351,    1879,    1272,
    2217,    1863,    2473,    2735,    3324,    2128,     886,    1221,    2838,    2273,
       0,    1112,    1827,     607,    1062,     357,    3764,    2393,    2861,    1749,
    3072,     768,    1941,    1434,    3112,    3018,    4576,    4865,    4676,    4494,
    4614,    3391,    3902,    4457,    5773,    3816,    5986,    5303,    5615,    5907,
    4260,   12038,   11629,   10776,   10693,    8833,    8692,    9589,    8451,    8990,
    8379,    7385,    8468,    6799,    7397,   10782,   12184,   11464,   11251,   11780,
   12389,   10590,   11111,   11874,   10138,   11466,   11045,   10931,    9118,    8619,
   10728,   11245,    6177,    5698,    5800,    6276,    6708,    6277,    6597,    7438,
    6600,    6086,    5716,    5484,    5382,    5446,    5778,    5988,    6467,    4815,
    5106,    5223,    5437,    5681,    5104,    4650,    5272,    6093,    7074,    4460,
    4335,    4293,    4486,    4842,    3910,    4080,    4571,    4795,    3450,    4035,
    3692,    3763,    4315,    3564,    3457,    3265,    2986,    2713,    3296,    3351,
    3781,    3713,    2614,    2928,    2849,    2860,    3113,    2124,    1826,    2395,
    1877,    2524,    2453,    2994,    1845,    1401,    1433,    2147,    1872,    1119,
       0,     818,    1559,    1668,     954,    2718,    2631,    1852,     980,    2544,
     680,    2454,    1999,    3364,    2899,    4506,    4284,    4606,    4015,    4009,
    2678,    3417,    3978,    5386,    3327,    5348,    4574,    5396,    5331,    3910,
   12312,   11908,   10478,   10330,    9092,    8672,    9569,    8196,    8970,    8228,
    7365,    8312,    6779,    7377,   10452,   11852,   11142,   10943,   11530,   11818,
   10290,   10410,   11303,    9909,   10895,   10474,   10568,    9098,    8599,   10157,
   10674,    6308,    5829,    5780,    6286,    6688,    5611,    6360,    7075,    6291,
    5849,    5574,    5659,    5311,    5402,    5758,    5722,    6025,    4795,    4889,
    5203,    5281,    5311,    5013,    4470,    4991,    5812,    6768,    4849,    4315,
    4202,    4205,    4561,    3890,    4047,    4444,    4668,    3807,    3754,    3672,
    3690,    4034,    3283,    3368,    3245,    2897,    3017,    3015,    3070,    3500,
    3432,    2482,    2597,    2568,    2638,    2773,    2174,    2308,    2185,    1784,
    2242,    2156,    2524,    1564,    2074,    1837,    1904,    1490,    1827,     818,
       0,    2098,    2034,    1541,    1946,    2875,    1080,     861,    1725,    1069,
    2722,    2420,    3686,    3095,    3998,    4041,    4098,    3684,    3766,    2435,
    3092,    3647,    4963,    3006,    5105,    4331,    5042,    4488,    3450,   11890,
   11481,   10631,   10755,    8685,    8782,    9921,    8424,    9343,    8653,    7634,
    8737,    7041,    7936,   10664,   12277,   11567,   11368,   11955,   13174,   10715,
   11503,   12659,   10334,   12239,   11830,   10993,    9657,    9048,   11501,   12030,
    6218,    5744,    5951,    6322,    7247,    6995,    7065,    7780,    7042,    6596,
    6298,    5336,    5428,    6003,    6144,    6354,    7185,    4861,    5472,    5707,
    5803,    6399,    5470,    5016,    5990,    6811,    7516,    4312,    4701,    4659,
    4965,    5422,    3956,    4287,    4651,    5053,    3302,    4753,    3995,    4129,
    5033,    4337,    3598,    3631,    3032,    2706,    3812,    4148,    4596,    4611,
    2980,    3444,    3747,    3226,    3944,    2475,    1868,    2813,    2459,    3069,
    3328,    3920,    2724,    1482,    1817,    3533,    2804,     607,    1559,    2261,
       0,     951,     625,    4161,    2332,    3266,    2286,    3626,    1130,    1536,
     981,    2861,    2829,    5169,    5421,    5269,    5048,    5168,    4082,    4456,
    5011,    6327,    4370,    6540,    5894,    6211,    6461,    4814,   12375,   11966,
   11116,   11241,    9170,    9267,   10407,    8909,    9829,    9139,    8119,    9223,
    7526,    8421,   11149,   12763,   12053,   11854,   12441,   13660,   11201,   11989,
   13145,   10820,   12725,   12316,   11479,   10142,    9534,   11987,   12516,    6703,
    6230,    6436,    6808,    7732,    7465,    7551,    8266,    7528,    7082,    6784,
    5821,    5914,    6489,    6629,    6839,    7670,    5347,    5957,    6193,    6288,
    6884,    5955,    5501,    6475,    7296,    8002,    4797,    5186,    5144,    5450,
    5907,    4442,    4772,    5137,    5539,    3787,    5238,    4480,    4614,    5518,
    4822,    4084,    4116,    3518,    3191,    4297,    4633,    5081,    5096,    3465,
    3929,    4191,    3711,    4325,    2960,    2353,    3298,    2944,    3554,    3675,
    4216,    3020,    1967,    2302,    3784,    3254,    1092,    1668,    2089,     749,
       0,     827,    3187,    1331,    2390,    2537,    3513,    1175,    1043,     578,
    2050,    2022,    5550,    5787,    5650,    5414,    5534,    4337,    4822,    5377,
    6693,    4736,    6906,    6249,    6594,    6214,    5180,   11640,   11231,   10381,
   10589,    8435,    8532,    9755,    8174,    9177,    8487,    7384,    8571,    6791,
    7686,   10414,   12111,   11401,   11202,   11789,   13008,   10549,   11337,   12493,
   10168,   12073,   11664,   10827,    9407,    8882,   11335,   11864,    5968,    5578,
    5701,    6148,    6997,    6576,    6885,    7614,    6547,    6033,    5663,    5086,
    5262,    5393,    5725,    5935,    6766,    4695,    5053,    5501,    5384,    5980,
    5051,    4597,    5571,    6392,    7021,    4062,    4282,    4240,    4546,    5003,
    3747,    4037,    4485,    4887,    3052,    4334,    3745,    3710,    4614,    3918,
    3432,    3212,    2866,    2456,    3393,    3729,    4177,    4192,    2561,    3025,
    3328,    2807,    3598,    2056,    1465,    2394,    2040,    2650,    2847,    3388,
    2192,    1063,    1398,    2956,    2426,     357,     954,    1541,     625,     823,
       0,    3442,    2154,    2547,    1709,    3282,     515,    1666,    1159,    2873,
    2640,    4816,    5057,    4905,    4762,    4856,    3509,    4170,    4725,    6041,
    4084,    6195,    5421,    5792,    6175,    4528,   13056,   12647,   11376,   11465,
    9851,    9555,   10452,    9314,    9853,    9242,    8248,    9331,    7662,    8260,
   11335,   12417,   11697,   11484,   12013,   12594,   10823,   11186,   12079,   10371,
   11671,   11250,   11268,    9351,    9482,   10933,   11450,    7588,    7067,    6663,
    7294,    7571,    6266,    7460,    8210,    6952,    6949,    6579,    6893,    6491,
    6309,    6218,    6383,    6680,    6098,    5858,    6086,    5984,    5966,    5616,
    5402,    5652,    6473,    7429,    5869,    5198,    4708,    4866,    5222,    5193,
    4998,    5434,    5658,    4799,    4415,    4610,    4626,    4695,    3944,    4624,
    4128,    4128,    4401,    3773,    3731,    4161,    4047,    3620,    3405,    3048,
    3594,    3278,    3763,    4012,    3331,    3212,    3062,    2549,    2201,    2725,
    3778,    3541,    1648,    2176,    3731,    2797,    1946,    3998,    3217,    3520,
       0,    4130,     793,    2581,     691,    2969,    3905,    3693,    4849,    3733,
    3827,    3785,    4118,    3099,    2559,    1873,    2507,    3025,    3936,    1663,
    3898,    2746,    5112,    3376,    1937,   14168,   13759,   12735,   12668,   10963,
   10979,   11834,   10453,   11256,   10566,    9756,   10650,    9169,    9959,   12741,
   14190,   13480,   13281,   13868,   15087,   12628,   13416,   14572,   12247,   14152,
   13743,   12906,   11742,   10961,   13414,   13943,    8136,    7657,    8020,    8235,
    9383,    8640,    8978,    9693,    8611,    8097,    7727,    7486,    7341,    7457,
    7789,    7999,    8830,    6774,    7117,    7620,    7448,    8044,    7115,    6661,
    7635,    8456,    9085,    6590,    6346,    6304,    6610,    7067,    5869,    6278,
    6564,    6966,    5580,    6398,    6036,    5774,    6678,    5982,    5511,    5276,
    4945,    4939,    5457,    5793,    6241,    6204,    4625,    5089,    5340,    4871,
    5604,    4120,    4146,    4458,    4104,    4714,    4944,    5485,    4171,    3127,
    3462,    4645,    4363,    2885,    2631,    2875,    2332,    1331,    2159,    4123,
       0,    2925,    3478,    4104,    2017,     916,    1423,    1025,    1011,    6875,
    6994,    6975,    6513,    6507,    5176,    5915,    6476,    7884,    5076,    7846,
    6159,    7856,    6805,    5350,   13021,   12612,   11299,   11151,    9816,    9520,
   10398,    9017,    9818,    9049,    8213,    9133,    7627,    8225,   11300,   12485,
   11765,   11552,   12081,   12502,   10891,   11094,   11987,   10439,   11579,   11158,
   11336,    9419,    9444,   10841,   11358,    7297,    6818,    6628,    7259,    7536,
    6295,    7181,    7896,    7020,    6670,    6395,    6648,    6406,    6223,    6606,
    6451,    6709,    5784,    5710,    6051,    6102,    5995,    5784,    5291,    5720,
    6541,    7497,    5915,    5163,    4973,    4934,    5290,    4879,    4963,    5399,
    5623,    4638,    4483,    4575,    4591,    4763,    4012,    4357,    4093,    3886,
    4085,    3786,    3791,    4229,    4288,    3471,    3418,    3150,    3559,    3457,
    3255,    3389,    3156,    2948,    3014,    2651,    2995,    2685,    3050,    2918,
    2404,    2105,    2672,    1852,    1080,    2705,    2390,    2447,     793,    2925,
       0,    1942,    1485,    1676,    3078,    2866,    4022,    2954,    4546,    4579,
    4635,    4004,    3353,    2667,    3406,    3967,    4730,    2457,    4692,    3540,
    5726,    4186,    2731,   11565,   11156,   10065,    9917,    8360,    7810,    8707,
    7569,    8108,    7497,    6503,    7586,    5917,    6515,    9590,   11302,   10582,
   10369,   10898,   11405,    9708,    9997,   10890,    9256,   10482,   10061,   10153,
    8236,    7737,    9744,   10261,    5893,    5416,    4918,    5549,    5826,    5198,
    5715,    6568,    5718,    5204,    4834,    5011,    4746,    4564,    4896,    5048,
    5512,    4225,    4224,    4341,    4672,    4726,    4339,    3768,    4317,    5138,
    6192,    3987,    3453,    3528,    3531,    3887,    3371,    3198,    3689,    3913,
    2945,    3080,    2810,    2881,    3360,    2609,    2575,    2383,    2088,    2155,
    2341,    2396,    2826,    2758,    1732,    1973,    1894,    1964,    2158,    1566,
    1477,    1492,     922,    1569,    1498,    2039,     890,    1243,    1006,    1447,
     917,    1478,     980,     861,    2150,    2413,    1709,    2541,    3478,    1942,
       0,    1849,    1561,    3277,    2868,    4241,    3730,    3585,    3548,    3679,
    3271,    3347,    2000,    2679,    3234,    4550,    2593,    4686,    3912,    4441,
    4669,    3037,   12364,   11955,   10684,   11128,    9159,    8863,    9760,    8622,
    9161,    8550,    7556,    8639,    6970,    7568,   10643,   11725,   11005,   10792,
   11321,   12257,   10131,   10652,   11742,    9679,   11334,   10913,   10576,    8659,
    8790,   10596,   11113,    6896,    6375,    5971,    6602,    6879,    5929,    6768,
    7621,    6260,    6257,    5887,    6201,    5799,    5617,    5526,    5691,    6155,
    5474,    5166,    5394,    5292,    5369,    4924,    4710,    4960,    5781,    6737,
    5177,    4506,    4016,    4174,    4530,    4560,    4306,    4742,    4966,    4107,
    3723,    3918,    3934,    4003,    3252,    3932,    3436,    3436,    3709,    3081,
    3039,    3469,    3355,    2928,    2713,    2356,    2902,    2586,    3071,    3320,
    2639,    2520,    2370,    1857,    1509,    2033,    3086,    2849,     956,    1484,
    3568,    2559,    1787,    3839,    3513,    3282,     691,    4104,    1485,    1889,
       0,    2810,    4201,    3989,    5136,    4426,    3135,    3093,    3426,    2518,
    2447,    1181,    1920,    2481,    3824,    1811,    3819,    2493,    4420,    3069,
    1714,   11813,   11404,   10551,   10484,    8608,    8705,    9649,    8269,    9050,
    8382,    7557,    8466,    6859,    7457,   10557,   12006,   11296,   11097,   11684,
   12903,   10444,   11171,   12388,   10063,   11968,   11559,   10722,    9178,    8679,
   11230,   11759,    5952,    5473,    5836,    6051,    6768,    6606,    6657,    7509,
    6660,    6146,    5776,    5259,    5157,    5506,    5838,    6048,    6879,    4590,
    5166,    5283,    5497,    6093,    5164,    4710,    5684,    6505,    7134,    4235,
    4395,    4353,    4659,    5116,    3685,    4094,    4380,    4782,    3225,    4447,
    3752,    3823,    4727,    3987,    3327,    3325,    2757,    2629,    3506,    3842,
    4290,    4253,    2674,    3138,    3332,    2920,    3466,    2169,    1601,    2507,
    2153,    2763,    2850,    3534,    2220,    1176,    1511,    2827,    2412,     768,
     680,    1092,    1130,    1129,     515,    2992,    2017,    2126,    1561,    2818,
       0,    1817,    1516,    2750,    2262,    4691,    4928,    4791,    4555,    4675,
    3358,    3963,    4518,    5834,    3877,    6028,    5254,    5735,    5534,    4321,
   13224,   12815,   11965,   12089,   10019,   10116,   11255,    9758,   10677,    9987,
    8968,   10071,    8375,    9270,   11998,   13611,   12901,   12702,   13289,   14508,
   12049,   12837,   13993,   11668,   13573,   13164,   12327,   10991,   10382,   12835,
   13364,    7552,    7078,    7285,    7656,    8581,    8313,    8399,    9114,    8376,
    7930,    7632,    6670,    6762,    7337,    7478,    7688,    8519,    6195,    6806,
    7041,    7137,    7733,    6804,    6350,    7324,    8145,    8850,    5646,    6035,
    5993,    6299,    6756,    5290,    5621,    5985,    6387,    4636,    6087,    5329,
    5463,    6367,    5671,    4932,    4965,    4366,    4040,    5146,    5482,    5930,
    5945,    4314,    4778,    5039,    4560,    5173,    3809,    3202,    4147,    3793,
    4403,    4513,    5054,    3858,    2816,    3151,    4622,    4092,    1941,    2506,
    2981,    1472,    1043,    1666,    4048,     916,    3163,    3375,    4286,    2007,
       0,     507,    1441,    1413,    6398,    6635,    6498,    6262,    6382,    5175,
    5670,    6225,    7541,    5584,    7754,    7087,    7442,    6987,    6028,   12717,
   12308,   11458,   11582,    9512,    9609,   10748,    9251,   10170,    9480,    8461,
    9564,    7868,    8763,   11491,   13104,   12394,   12195,   12782,   14001,   11542,
   12330,   13486,   11161,   13066,   12657,   11820,   10484,    9875,   12328,   12857,
    7045,    6571,    6778,    7149,    8074,    7806,    7892,    8607,    7869,    7423,
    7125,    6163,    6255,    6830,    6971,    7181,    8012,    5688,    6299,    6534,
    6630,    7226,    6297,    5843,    6817,    7638,    8343,    5139,    5528,    5486,
    5792,    6249,    4783,    5114,    5478,    5880,    4129,    5580,    4822,    4956,
    5860,    5164,    4425,    4458,    3859,    3533,    4639,    4975,    5423,    5438,
    3807,    4271,    4532,    4053,    4666,    3302,    2695,    3640,    3286,    3896,
    4006,    4547,    3351,    2309,    2644,    4115,    3585,    1434,    1999,    2420,
     965,     578,    1159,    3663,    1423,    2866,    2868,    4161,    1500,     507,
       0,    1948,    1920,    5891,    6128,    5991,    5755,    5875,    4668,    5163,
    5718,    7034,    5077,    7247,    6580,    6935,    7168,    5521,   14697,   14288,
   13246,   13179,   11492,   11490,   12345,   10964,   11767,   11077,   10267,   11161,
    9680,   10470,   13252,   14701,   13991,   13792,   14379,   15598,   13139,   13927,
   15083,   12758,   14663,   14254,   13417,   12253,   11472,   13925,   14454,    8647,
    8168,    8531,    8746,    9894,    9301,    9489,   10204,    9538,    9092,    8722,
    7997,    7852,    8427,    8951,    9000,    9715,    7285,    8132,    8131,    8524,
    9001,    8277,    7713,    8581,    9618,   10012,    7119,    7262,    7466,    7692,
    8229,    6380,    6789,    7075,    7477,    6109,    7187,    6547,    6764,    7467,
    6682,    6022,    6438,    5456,    5450,    6265,    6567,    6993,    6992,    5556,
    5840,    6027,    5861,    6161,    4912,    4667,    5267,    5182,    5485,    5545,
    6304,    5028,    3972,    4382,    5819,    5134,    3290,    3364,    3739,    2785,
    2036,    2863,    4825,    1025,    4117,    4564,    5205,    2750,    1427,    1934,
       0,    1131,    7386,    7623,    7486,    7250,    7370,    6284,    6658,    7213,
    8529,    6572,    8742,    8096,    8430,    7836,    6451,   14534,   14130,   12700,
   12633,   11379,   10944,   11799,   10418,   11221,   10531,    9721,   10615,    9134,
    9924,   12706,   14155,   13445,   13246,   13833,   15052,   12593,   13381,   14537,
   12212,   14117,   13708,   12871,   11707,   10926,   13379,   13908,    8101,    7622,
    7985,    8200,    9348,    8755,    8943,    9658,    8992,    8546,    8176,    7451,
    7306,    7881,    8111,    8321,    9152,    6739,    7439,    7585,    7770,    8366,
    7437,    6983,    7957,    8778,    9466,    6718,    6668,    6626,    6932,    7389,
    5834,    6243,    6529,    6931,    5933,    6641,    6001,    6096,    6921,    6136,
    5476,    5598,    4910,    4904,    5719,    6021,    6447,    6446,    4947,    5294,
    5481,    5193,    5615,    4366,    4121,    4721,    4426,    4939,    4999,    5758,
    4482,    3426,    3784,    4967,    4588,    3048,    2829,    3059,    2771,    2022,
    2782,    3733,    1011,    2954,    3800,    4426,    2267,    1413,    1920,    1101,
       0,    6840,    7077,    6940,    6704,    6824,    5498,    6112,    6667,    7983,
    5398,    8168,    6481,    7884,    7099,    5672,    9518,    9114,    7684,    6983,
    7396,    5853,    6118,    5336,    5540,    4881,    4593,    4965,    4847,    4192,
    7051,    8054,    7334,    7121,    7650,    8121,    6460,    6713,    7606,    6008,
    7198,    6777,    6905,    4988,    5028,    6460,    6977,    5174,    4653,    4249,
    4680,    4608,    2642,    3644,    3777,    3486,    3540,    3751,    4815,    4180,
    3586,    3281,    3035,    2999,    3855,    3103,    3634,    2721,    2342,    2547,
    2684,    2113,    2321,    3393,    3958,    2887,    2357,    2149,    1976,    3297,
    3003,    3123,    3292,    3585,    1656,    2715,    2314,    1516,    1566,    2847,
    2427,    3339,    3814,    2019,    1679,    1162,    1141,    3088,    2316,    1488,
    2907,    1217,    3516,    4069,    2695,    2865,    2204,    2104,    1617,    2773,
    3767,    3417,    2569,    2696,    4639,    4545,    4075,    5235,    5612,    4816,
    3827,    6885,    4546,    3590,    3135,    5085,    6569,    6062,    7604,    7093,
       0,    1949,    1199,    2123,    2695,    2161,    1417,    2548,    3162,    2374,
    3588,    3272,    1094,    4029,    2597,   11296,   10886,    9425,    9386,    9013,
    7377,    8059,    6921,    7460,    6849,    6563,    6914,    6365,    5867,    8942,
    9284,    8564,    8351,    8880,   10511,    7690,    8211,    8895,    7238,    9588,
    9167,    8135,    6218,    6258,    7860,    8388,    6750,    6229,    5825,    6198,
    6018,    4139,    5242,    5276,    4896,    5058,    5269,    6288,    5653,    5467,
    4799,    4484,    4409,    5328,    4598,    5244,    4208,    3858,    4041,    4179,
    3555,    3767,    5099,    5431,    4360,    3853,    3995,    3658,    4622,    4368,
    4596,    4820,    4512,    3502,    3980,    3787,    3198,    3070,    3923,    3498,
    3977,    4381,    3090,    2682,    2839,    2577,    3746,    2779,    2235,    3313,
    1964,    4033,    4487,    3442,    3412,    2951,    2377,    2364,    3060,    4290,
    3999,    2317,    2665,    4930,    4284,    4041,    5602,    5865,    5057,    3655,
    6974,    4482,    3548,    2963,    5043,    6723,    6216,    7693,    7182,    1949,
       0,     754,     596,    1060,    1777,    1170,     569,    1560,    2032,    1986,
    1345,    1948,    2073,    1712,   10541,   10131,    8670,    8177,    8258,    6622,
    7304,    6166,    6705,    6075,    5787,    6159,    5610,    5112,    8187,    8529,
    7809,    7596,    8125,    9315,    6935,    7456,    8140,    6483,    8392,    7971,
    7380,    5463,    5503,    7105,    7633,    6022,    5501,    5171,    5443,    5263,
    3384,    4487,    4521,    4141,    4303,    4514,    5737,    5082,    4506,    4044,
    3729,    3654,    4777,    4025,    4556,    3453,    3103,    3286,    3606,    2800,
    3012,    4344,    4880,    3809,    3279,    3071,    2903,    4105,    3806,    4045,
    4212,    3854,    2578,    3433,    3236,    2443,    2488,    3265,    2840,    3319,
    3723,    2432,    2024,    2084,    1919,    3088,    2121,    1577,    2655,    1306,
    3375,    3908,    2784,    2954,    2293,    2193,    1706,    2862,    3856,    3506,
    2520,    2785,    4653,    4566,    4164,    5324,    5588,    4902,    4061,    6861,
    4635,    3639,    3369,    5143,    6601,    6094,    7580,    7069,    1194,     754,
       0,    1086,    1815,    2248,    1503,    1324,    2045,    2457,    2471,    2100,
    1193,    2857,    2445,   11215,   10811,    9381,    8680,    8982,    7550,    7815,
    7033,    7237,    6578,    6290,    6662,    6703,    5889,    8748,    9616,    8896,
    8683,    9212,    9805,    8022,    8397,    9227,    7570,    8882,    8461,    8467,
    6550,    6590,    8144,    8661,    6924,    6403,    5999,    6477,    6350,    4339,
    5341,    5474,    5228,    5289,    5464,    6462,    5806,    5292,    5131,    4732,
    4741,    5502,    4772,    5320,    4540,    4039,    4296,    4353,    3810,    4099,
    5090,    5605,    4534,    4027,    4169,    4187,    4796,    4530,    4770,    4994,
    4686,    3676,    4154,    3961,    3727,    3244,    4097,    3622,    4247,    4520,
    3264,    2856,    3395,    2751,    3739,    2953,    2409,    3709,    2138,    3909,
    4359,    3450,    3284,    2930,    2249,    1914,    2932,    4162,    3871,    1929,
    2537,    4662,    4015,    3772,    5334,    5597,    4911,    3210,    6513,    4004,
    3420,    2518,    4695,    6461,    6088,    7425,    6835,    2123,     596,    1086,
       0,    1044,    1340,     672,     897,    1892,    1666,    2318,    1621,    2280,
    2378,    1346,   11943,   11539,   10109,    9408,    9568,    8278,    8543,    7761,
    7965,    7306,    7018,    7390,    7289,    6617,    9476,   10345,    9625,    9412,
    9941,   10533,    8751,    9125,    9956,    8299,    9610,    9189,    9196,    7279,
    7319,    8872,    9389,    7496,    6975,    6571,    7063,    7324,    5067,    6069,
    6202,    5998,    6017,    6029,    7034,    6392,    5878,    6064,    5460,    5481,
    6074,    5344,    5906,    5273,    4767,    5024,    4925,    4538,    5016,    5818,
    6157,    5106,    4599,    4741,    4759,    5354,    5114,    5342,    5566,    5087,
    4248,    4726,    4533,    4299,    3816,    4669,    4208,    4361,    4689,    3836,
    3428,    3967,    3323,    3908,    3715,    2981,    3882,    2710,    4074,    4266,
    3619,    3343,    3372,    2845,    2521,    3013,    4032,    3902,    1936,    2464,
    4559,    4009,    3758,    5231,    5494,    4808,    2555,    6507,    3353,    3347,
    2512,    4689,    6358,    6000,    7322,    6811,    2695,    1060,    1815,    1042,
       0,    1385,    1299,     490,    1421,    1046,    1383,     609,    3009,    1337,
     713,   11872,   11468,   10038,    9200,    8652,    8282,    8335,    7756,    7757,
    7098,    6960,    7182,    6373,    6409,   10044,   10210,    9490,    9277,    9806,
   10338,    8616,    8930,    9823,    8164,    9415,    8994,    9061,    7144,    7184,
    8677,    9194,    6366,    5887,    5604,    6147,    6512,    4859,    5861,    5986,
    5790,    5409,    5134,    5717,    5432,    4962,    5181,    5252,    5155,    4853,
    4449,    4990,    4841,    4559,    4579,    4030,    4330,    4477,    5610,    4810,
    4139,    3671,    3829,    4185,    3948,    3939,    4375,    4599,    3740,    3378,
    3551,    3567,    3658,    2907,    3426,    3069,    2955,    3342,    2736,    2536,
    3124,    2648,    2540,    2368,    2011,    2535,    1671,    2668,    2919,    2225,
    1996,    2025,    1439,    1175,    1666,    2685,    2555,     589,    1117,    3153,
    2675,    2352,    3825,    4088,    3402,    1873,    5176,    2667,    2000,    1181,
    3358,    4952,    4594,    5916,    5405,    2161,    1915,    2248,    1340,    1385,
       0,     742,    1311,    2670,     703,    2724,    1950,    3446,    2707,    1157,
   10935,   10531,    9101,    8400,    8276,    7270,    7535,    6753,    6957,    6298,
    6010,    6382,    5997,    5609,    8468,    9471,    8751,    8538,    9067,    9538,
    7877,    8130,    9023,    7425,    8615,    8194,    8322,    6405,    6445,    7877,
    8394,    6207,    5686,    5282,    5771,    6186,    4059,    5061,    5194,    4903,
    5009,    4740,    5745,    5100,    4586,    4775,    4452,    4416,    4785,    4055,
    4614,    4215,    3759,    4016,    3636,    3530,    3738,    4810,    4888,    3817,
    3310,    3452,    3470,    4079,    3824,    4053,    4277,    4240,    2959,    3437,
    3244,    3010,    2527,    3380,    2916,    3470,    3842,    2547,    2139,    2678,
    2034,    3055,    2236,    1692,    3031,    1421,    3216,    3661,    2740,    2596,
    2252,    1571,    1236,    2254,    3484,    3193,    1331,    1859,    3895,    3417,
    3094,    4567,    4830,    4144,    2612,    5915,    3406,    2742,    1920,    4097,
    5694,    5336,    6658,    6147,    1417,    1170,    1503,     672,    1299,     742,
       0,    1152,    2466,     956,    2650,    1876,    2702,    2604,    1061,   11866,
   11456,    9995,    9574,    9612,    7947,    8629,    7491,    8030,    7419,    7133,
    7484,    6935,    6437,    9512,    9854,    9134,    8921,    9450,   10699,    8260,
    8781,    9465,    7808,    9776,    9355,    8705,    6788,    6828,    8430,    8958,
    7349,    6828,    6424,    6768,    6588,    4709,    5812,    5846,    5466,    5628,
    5839,    6887,    6252,    6066,    5369,    5054,    4979,    5927,    5197,    5843,
    4778,    4428,    4611,    4778,    4125,    4337,    5669,    6030,    4959,    4452,
    4594,    4612,    5221,    4967,    5195,    5419,    5111,    4101,    4579,    4386,
    4152,    3669,    4522,    4097,    4380,    4653,    3689,    3281,    3409,    3176,
    3872,    3378,    2834,    3846,    2563,    4042,    4230,    3583,    3307,    3431,
    2750,    2415,    2977,    3996,    3866,    1900,    2428,    4702,    3978,    3735,
    5397,    5648,    4820,    3001,    6476,    3828,    3311,    2481,    4658,    6486,
    5979,    7768,    6798,    2548,     569,    1324,     897,     490,    1311,    1152,
       0,    1414,    1492,    1549,     775,    2518,    1503,    1159,   11916,   11512,
   10082,    9381,    9794,    8251,    8516,    7734,    7938,    7279,    6991,    7363,
    7515,    6590,    9449,    9777,    9057,    8844,    9292,    9659,    8183,    8251,
    9144,    7731,    8736,    8315,    8628,    6711,    6751,    7998,    8515,    7961,
    7404,    7170,    7289,    7297,    5040,    6042,    6175,    5971,    5990,    6301,
    7419,    6748,    6129,    6089,    5433,    5454,    6459,    5668,    6157,    5246,
    4740,    4997,    5481,    4511,    4831,    5791,    6725,    5656,    5294,    5148,
    5012,    5918,    5651,    5892,    5848,    5808,    4655,    5276,    5083,    4520,
    4366,    5219,    4743,    5273,    5859,    4386,    3978,    4161,    3873,    4993,
    4075,    3531,    4609,    3260,    5182,    5627,    4706,    4562,    4247,    3540,
    3346,    4384,    5409,    5163,    3313,    3743,    5779,    5301,    4978,    6451,
    6714,    6028,    3936,    7823,    4730,    4627,    3812,    5988,    7578,    7220,
    8542,    8031,    3162,    1560,    2042,    1892,    1421,    2626,    2466,    1414,
       0,    2423,     425,    1459,    3000,    1531,    2090,   11876,   11472,   10042,
    9341,    9217,    8211,    8476,    7694,    7898,    7239,    6951,    7323,    6938,
    6550,    9409,   10428,    9708,    9495,   10024,   10479,    8834,    9071,    9964,
    8382,    9556,    9135,    9279,    7362,    7402,    8818,    9335,    7074,    6595,
    6269,    6712,    7177,    5000,    6002,    6135,    5860,    5950,    5699,    6425,
    6041,    5527,    5846,    5393,    5373,    5561,    5014,    5555,    5206,    4700,
    4957,    4595,    4471,    4695,    5751,    5475,    4799,    4336,    4494,    4628,
    4656,    4604,    5035,    5259,    4405,    3960,    4216,    4210,    4168,    3486,
    4134,    3734,    3663,    4007,    3401,    3101,    3701,    3192,    3226,    3033,
    2654,    3200,    2383,    3376,    3584,    2933,    2661,    2690,    2147,    1926,
    2331,    3350,    3220,    1254,    1782,    3861,    3327,    3060,    4533,    4796,
    4110,    1660,    5076,    2457,    2665,    1830,    4007,    5660,    5302,    6624,
    5398,    2358,    2032,    2451,    1532,    1046,     703,     940,    1458,    2423,
       0,    2385,    1611,    3646,    2469,     763,   12342,   11938,   10508,    9807,
   10220,    8677,    8942,    8160,    8364,    7705,    7417,    7789,    7941,    7016,
    9875,   10203,    9483,    9270,    9718,   10085,    8609,    8677,    9570,    8157,
    9162,    8741,    9054,    7137,    7177,    8424,    8941,    8387,    7830,    7596,
    7715,    7723,    5466,    6468,    6601,    6397,    6416,    6727,    7845,    7174,
    6555,    6515,    5859,    5880,    6885,    6094,    6583,    5672,    5166,    5423,
    5907,    4937,    5257,    6217,    7151,    6082,    5720,    5574,    5438,    6344,
    6077,    6318,    6274,    6426,    5081,    5702,    5509,    4946,    4792,    5645,
    5169,    5725,    6028,    4812,    4404,    4587,    4299,    5247,    4501,    3957,
    5221,    3686,    5417,    5605,    4958,    4682,    4681,    3966,    3772,    4352,
    5371,    5241,    3275,    3803,    5923,    5348,    5105,    6595,    6858,    6172,
    3898,    7846,    4692,    4686,    3851,    6028,    7722,    7354,    8686,    8168,
    3588,    1986,    2468,    2395,    1383,    2724,    2650,    1549,     425,    2385,
       0,    1421,    3426,    1302,    2052,   12208,   11804,   10374,    9673,   10086,
    8543,    8808,    8026,    8230,    7571,    7283,    7655,    7807,    6882,    9741,
   10610,    9890,    9677,   10206,   10798,    9016,    9390,   10283,    8564,    9875,
    9454,    9461,    7544,    7584,    9137,    9654,    8073,    7552,    7148,    7581,
    7364,    5332,    6334,    6467,    6242,    6282,    6593,    7611,    6957,    6421,
    6145,    5725,    5746,    6651,    5921,    6449,    5538,    5032,    5289,    5502,
    4803,    5113,    6083,    6722,    5683,    5176,    5318,    5304,    5919,    5681,
    5919,    6143,    5652,    4825,    5303,    5110,    4876,    4393,    5246,    4773,
    4926,    5254,    4413,    4005,    4544,    3900,    4473,    4280,    3558,    4447,
    3287,    4639,    4831,    4184,    3908,    3937,    3410,    3086,    3578,    4597,
    4467,    2501,    3029,    5124,    4574,    4323,    5796,    6059,    5373,    2746,
    6159,    3540,    3912,    3077,    5254,    6923,    6565,    7887,    6481,    3272,
    1345,    2097,    1607,     609,    1950,    1876,     775,    1459,    1611,    1421,
       0,    3292,     918,     652,    9262,    8858,    7428,    6727,    7133,    5470,
    5862,    5014,    5284,    4625,    4337,    4709,    4458,    3936,    6795,    7593,
    6873,    6660,    7189,    7865,    5999,    6457,    7350,    5547,    6942,    6521,
    6444,    4527,    4567,    6204,    6721,    4870,    4349,    3961,    4291,    4111,
    2232,    3335,    3369,    2989,    3151,    3362,    4544,    3973,    3354,    2892,
    2577,    2502,    3691,    2930,    3344,    2301,    1951,    2134,    2651,    1648,
    1860,    3137,    4071,    3066,    2554,    2100,    1941,    3784,    3316,    3302,
    2982,    4072,    1860,    3202,    2801,    1580,    2018,    3334,    2879,    3791,
    4266,    2471,    2131,    1614,    1595,    3540,    2768,    2263,    3359,    2342,
    4047,    4618,    3671,    3841,    3180,    3229,    2732,    3776,    4743,    4393,
    3514,    3815,    5571,    5396,    5115,    6211,    6506,    5792,    4979,    7779,
    5806,    4441,    4287,    5905,    7519,    7012,    8498,    7987,    1094,    1948,
    1193,    2280,    3009,    3262,    2519,    2518,    3231,    3659,    3657,    3292,
       0,    4162,    3581,   12939,   12535,   11105,   10404,   10817,    9274,    9539,
    8757,    8961,    8302,    8014,    8386,    8538,    7613,   10472,   11226,   10506,
   10293,   10713,   11080,    9632,    9672,   10565,    9180,   10157,    9736,   10077,
    8160,    8200,    9419,    9936,    8830,    8309,    7905,    8312,    8121,    6063,
    7065,    7198,    6994,    7013,    7324,    8353,    7688,    7152,    6902,    6456,
    6477,    7408,    6661,    7180,    6269,    5763,    6020,    6242,    5534,    5870,
    6814,    7479,    6440,    5933,    6075,    6035,    6650,    6412,    6676,    6900,
    6409,    5582,    6039,    5857,    5633,    5133,    5982,    5504,    5657,    6011,
    5153,    4748,    5301,    4657,    5230,    5037,    4301,    5204,    4030,    5370,
    5588,    4927,    4665,    4694,    4141,    3843,    4335,    5354,    5224,    3258,
    3786,    5855,    5331,    4488,    6527,    6214,    6104,    3349,    6805,    4176,
    4669,    3085,    5534,    6859,    6647,    7794,    7108,    4023,    2102,    2828,
    2338,    1340,    2706,    2611,    1532,    1503,    2518,    1308,     889,    4023,
       0,    1676,   12047,   11643,   10213,    9512,    9388,    8382,    8647,    7865,
    8069,    7410,    7122,    7494,    7109,    6721,    9580,   10651,    9931,    9718,
   10247,   10650,    9057,    9242,   10135,    8605,    9727,    9306,    9502,    7585,
    7625,    8989,    9506,    7425,    6868,    6852,    6883,    7760,    5171,    6173,
    6306,    6083,    6121,    5870,    6877,    6212,    5698,    5955,    5564,    5585,
    5943,    5185,    5726,    5377,    4871,    5128,    4766,    4642,    4918,    5922,
    6058,    4970,    4490,    4632,    4650,    5071,    4936,    5206,    5430,    4988,
    4131,    4563,    4381,    4190,    3657,    4506,    4028,    4078,    4529,    3677,
    3272,    3858,    3214,    3663,    3588,    2825,    3783,    2554,    3791,    4167,
    3348,    3204,    3233,    2562,    2422,    2914,    3933,    3717,    1837,    2240,
    4276,    3798,    3475,    4948,    5211,    4525,    1937,    5350,    2731,    3124,
    2309,    4485,    6075,    5717,    6451,    5672,    2529,    1712,    2445,    1346,
     713,    1127,    1111,    1159,    2090,     763,    2052,     757,    3639,    1647,
       0
];
